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详情见代码- -