P2157 [SDOI2009]学校食堂状压DP-白红宇

P2157 [SDOI2009]学校食堂状压DP

阅读量：5144 次

发布时间：2019-06-13

本文共 2408 字，大约阅读时间需要 8 分钟。

题意：　　

　　排队买饭，时间为前一个人和后一个人的异或和，每个人允许其后面B【i】个人先买到饭，问最少的总用时。

思路：

　　用dp【i】【j】【k】表示1～i-1已经买好饭了，第i个人后面买饭情况为j，最后一个打饭的是i+k。

#include 
      
       #include  
       
        #include  
        
         #include   
         
          #include   
          
           #include   
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     #include 
                      
                       #include 
                       
                        using namespace std;#define lson (l , mid , rt << 1)#define rson (mid + 1 , r , rt << 1 | 1)#define debug(x) cerr << #x << " = " << x << "\n";#define pb push_back#define pq priority_queuetypedef long long ll;typedef unsigned long long ull;//typedef __int128 bll;typedef pair
                        
                          pll;typedef pair
                         
                           pii;typedef pair
                          
                            p3;//priority_queue
                           
                             q;//这是一个大根堆q//priority_queue
                            
                             
                              ,greater
                              
                                >q;//这是一个小根堆q#define fi first#define se second//#define endl '\n'#define OKC ios::sync_with_stdio(false);cin.tie(0)#define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行#define REP(i , j , k) for(int i = j ; i < k ; ++i)#define max3(a,b,c) max(max(a,b), c);#define min3(a,b,c) min(min(a,b), c);//priority_queue

, greater

>que;const ll mos = 0x7FFFFFFF; //2147483647const ll nmos = 0x80000000; //-2147483648const int inf = 0x3f3f3f3f;const ll inff = 0x3f3f3f3f3f3f3f3f; //18const int mod = 1000000007;const double esp = 1e-8;const double PI=acos(-1.0);const double PHI=0.61803399; //黄金分割点const double tPHI=0.38196601;template

inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x;}/*-----------------------showtime----------------------*/ const int maxn = 1009; int dp[maxn][1<<8][20]; int A[maxn],B[maxn]; int cal(int q,int h){ if(q == 0) return 0; return A[q] ^ A[h]; } void solve(){ int n; scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d%d", &A[i], &B[i]); memset(dp, inf, sizeof(dp)); dp[1][0][7] = 0; for(int i=1; i<=n; i++) for(int j=0; j<(1<<8); j++){ for(int k=-8; k<=7; k++) if(dp[i][j][k+8] < inf){ if(j & 1) dp[i+1][j>>1][k+7] = min(dp[i+1][j>>1][k+7], dp[i][j][k+8]); else { int mx = inf; for(int h = 0; h<=7; h++) if(! (j & (1<

mx) break; mx = min(mx, i + h + B[i+h]); int tmp = dp[i][j][k + 8] + cal(i + k, i + h); dp[i][j | (1 << h)][h + 8] = min(dp[i][j | (1 << h)][h + 8], tmp); } } } } int ans = inf; for(int i=0; i<=8; i++) ans = min(ans, dp[n+1][0][i]); cout<

View Code

转载于:https://www.cnblogs.com/ckxkexing/p/10348316.html

你可能感兴趣的文章