1 # include <cstdio>
2 # include <cstring>
3 # include <algorithm>
4 using namespace std;
5 struct node
6 {
7 int h,c,maxh;
8 }data[401];
9 bool cmp(const node &a,const node &b)
10 {
11 return a.maxh<b.maxh;
12 }
13 bool dp[40001];
14 int q[40001][2];
15 int main()
16 {
17 int num,maxnum=-1;
18 scanf("%d",&num);
19 for(int i=0;i<num;i++)
20 scanf("%d%d%d",&data[i].h,&data[i].maxh,&data[i].c);
21 sort(data,data+num,cmp);
22 maxnum=data[num-1].maxh;
23 memset(dp,false,sizeof(dp));
24 memset(q,-1,sizeof(q));
25 dp[0]=true;
26 for(int i=0;i<num;i++)
27 {
28 for(int j=0;j<=data[i].maxh;j++)
29 {
30 if(!dp[j]&&j-data[i].h>=0&&dp[j-data[i].h])
31 {
32 if(q[j-data[i].h][0]!=i)
33 {
34 q[j][0]=i;
35 q[j][1]=1;
36 dp[j]=true;
37 }
38 else if(q[j-data[i].h][1]<data[i].c)
39 {
40 q[j][0]=i;
41 q[j][1]=q[j-data[i].h][1]+1;
42 dp[j]=true;
43 }
44 }
45 }
46 }
47 for(int i=maxnum;i>=0;i--)
48 {
49 if(dp[i])
50 {
51 printf("%d\n",i);
52 break;
53 }
54 }
55 return 0;
56
57 }
58
題目簡要解釋一下
奶牛們用k種積木搭建一個塔，每種積木有一定的個數和一定的高度。還有就是每種積木最高不能超過高度hi，問最高能搭到的高度
這題可以轉化為部分背包模型，先按照h對積木進行排序,狀態dp[i][j]表示使用了前i種木塊能否搭建到j的高度。
狀態轉移為
dp[i][j]=dp[i-1][j-k*height(i)],k<=num[i],j<h[i]
直接暴力DP復雜度高達n
3 ，DP的時候從前向后更新，并且開辟一個數組記錄當前位置已經更新的次數，可以將復雜度將為n
2詳情見代碼- -