经典动态规划 dp Rqnoj 57

感觉学过背包的话应该就很容易做了，优先级人数最多，时间最少，那么泡到n个妹妹就有相应的最少时间，所以要开一个数组存储该人数下时间最小。。。

仅此。。。

View Code

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 using namespace std;
 5 const int INF=1000000;
 6 const int N = 1002;
 7 int rmb[N],rp[N],tim[N];
 8 int dp[N][120][120],num[N];
 9 int Min(int a,int b)
10 {
11     return a<b?a:b;
12 }
13 int main()
14 {
15     int n,m,r;
16     while(scanf("%d",&n)!=EOF)
17     {
18         for(int i=1; i<=n; i++)
19             scanf("%d%d%d",&rmb[i],&rp[i],&tim[i]);
20         scanf("%d%d",&m,&r);
21         for(int k=1; k<=n; k++)
22         {
23             for(int i=0; i<=m; i++)
24             {
25                 for(int j=0; j<=r; j++)
26                 {
27                         dp[k][i][j]=INF;
28                 }
29             }
30         }
31         dp[0][0][0]=0;
32         for(int i=0; i<=n; i++)num[i]=INF;
33         for(int i=1; i<=n; i++)
34         {
35 
36             for(int j=m; j>=rmb[i]; j--)
37             {
38                 for(int k=r; k>=rp[i]; k--)
39                 {
40                     for(int z=i; z>=1; z--)
41                     {
42                         if(dp[z-1][j-rmb[i]][k-rp[i]]+tim[i]<dp[z][j][k])
43                         {
44                             dp[z][j][k]=dp[z-1][j-rmb[i]][k-rp[i]]+tim[i];
45                             num[z]=Min(num[z],dp[z][j][k]);
46                         }
47                     }
48                 }
49             }
50         }
51         int i;
52         for(i=n; i>=0; i--)if(num[i]<INF)break;
53         printf("%d\n",num[i]);
54     }
55     return 0;
56 }