洛谷P2577 [ZJOI2005]午餐打饭时间作为容量DP-白红宇

洛谷P2577 [ZJOI2005]午餐打饭时间作为容量DP

阅读量：5052 次

发布时间：2019-06-12

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

）逼着自己做DP

题意：

　　有n个人打饭，每个人都有打饭时间和吃饭时间。有两个打饭窗口，问如何安排可以使得总用时最少。

思路：

　　1）可以发现吃饭时间最长的要先打饭。（我也是看别人题解才知道）

　　2）然后就是对于前i个人，他不是在一号窗口打饭，就是在二号窗口打饭。所以用dp[i][j]表示前i个人，在一号窗口打饭j时间的总用时。因为dp[i][k = sum - 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 = 1e9+7;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 = 209; int dp[maxn][maxn*maxn],sum[maxn]; struct node { int t,w; }a[maxn]; bool cmp(node a,node b){ return a.w > b.w; }int main(){ int n; scanf("%d", &n); for(int i=1; i<=n; i++){ scanf("%d%d", &a[i].t, &a[i].w); } sort(a+1,a+1+n,cmp); for(int i=1; i<=n; i++) sum[i] = sum[i-1] + a[i].t; memset(dp, inf, sizeof(dp)); dp[0][0] = 0; for(int i=1; i<=n; i++){ for(int j=sum[i]; j>=0; j--){ if(j >= a[i].t)dp[i][j] = min(dp[i][j], max(dp[i-1][j-a[i].t], j + a[i].w)); dp[i][j] = min(dp[i][j], max(dp[i-1][j], sum[i] - j + a[i].w)); } } int ans = inf; for(int i=0; i<= sum[n]; i++) ans = min(ans, dp[n][i]); printf("%d\n", ans); return 0;}

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

你可能感兴趣的文章