Advertisement
MarioYC

UVA 12432 - Inked Carpets

Jun 6th, 2012
366
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.54 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <limits>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <map>
  7.  
  8. using namespace std;
  9.  
  10. int L,M,D,cost[51];
  11.  
  12. vector<int> x,to[2002],color[2002],price[2002];
  13.  
  14. bool done[2002][51][3];
  15. pair<long long, int> memo[2002][51][3];
  16.  
  17. pair<long long, int> solve(int pos, int last, int cont){
  18.     if(x[pos] == L) return make_pair(0LL,0);
  19.    
  20.     pair<long long, int> &ret = memo[pos][last][cont];
  21.    
  22.     if(!done[pos][last][cont]){
  23.         done[pos][last][cont] = true;
  24.        
  25.         ret = make_pair(numeric_limits<long long>::max(),numeric_limits<int>::max());
  26.         pair<long long, int> aux;
  27.        
  28.         for(int i = 1;i <= M;++i){
  29.             aux = solve(pos + 1,i,0);
  30.             aux.first += (long long)(x[pos + 1] - x[pos]) * cost[i];
  31.             aux.second += (i != last? 1 : 0);
  32.            
  33.             ret = min(ret,aux);
  34.         }
  35.        
  36.         for(int i = to[pos].size() - 1;i >= 0;--i){
  37.             aux = solve(to[pos][i],color[pos][i],color[pos][i] == last? min(cont + 1,2) : 1);
  38.             aux.first += price[pos][i] - (cont == 2? min(price[pos][i],D) : 0);
  39.             aux.second += (color[pos][i] != last? 1 : 0);
  40.            
  41.             ret = min(ret,aux);
  42.         }
  43.     }
  44.    
  45.     return ret;
  46. }
  47.  
  48. int main(){
  49.     int T,N;
  50.     int s[1000],e[1000],c[1000],p[1000];
  51.     map<int,int> id;
  52.    
  53.     scanf("%d",&T);
  54.    
  55.     for(int tc = 1;tc <= T;++tc){
  56.         scanf("%d %d %d %d",&L,&N,&M,&D);
  57.        
  58.         for(int i = 1;i <= M;++i)
  59.             scanf("%d",&cost[i]);
  60.        
  61.         x.clear();
  62.         x.push_back(0);
  63.         x.push_back(L);
  64.        
  65.         for(int i = 0;i < N;++i){
  66.             scanf("%d %d %d %d",&s[i],&e[i],&c[i],&p[i]);
  67.             x.push_back(s[i] - 1);
  68.             x.push_back(e[i]);
  69.         }
  70.        
  71.         sort(x.begin(),x.end());
  72.        
  73.         int sz = unique(x.begin(),x.end()) - x.begin();
  74.        
  75.         id.clear();
  76.        
  77.         for(int i = 0;i < sz;++i){
  78.             id[ x[i] ] = i;
  79.             to[i].clear();
  80.             color[i].clear();
  81.             price[i].clear();
  82.         }
  83.        
  84.         for(int i = 0;i < N;++i){
  85.             int j = id[ s[i] - 1 ];
  86.            
  87.             to[j].push_back(id[ e[i] ]);
  88.             color[j].push_back(c[i]);
  89.             price[j].push_back(p[i]);
  90.         }
  91.        
  92.         memset(done,0,sizeof done);
  93.         pair<long long, int> ans = solve(0,0,0);
  94.        
  95.         printf("Case %d: %lld %d\n",tc,ans.first,ans.second - 1);
  96.     }
  97.    
  98.     return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement