dp入门题目
分类:
IT文章
•
2023-11-29 20:38:07
本文文旨,如题...
转载请注明出处...
HDOJ 1176 免费馅饼
http://acm.hdu.edu.cn/showproblem.php?pid=1176
类似数塔,从底往上推,每次都是从下面三个中选最大的
1 #include<cstdio>
2 #include<cstring>
3 #define MAXN 100005
4 int dp[MAXN][11];//第i秒第j个位置的馅饼数
5 int max1(int a,int b)
6 {
7 return a>b?a:b;
8 }
9 int max2(int a,int b,int c)
10 {
11 return a>b?(a>c?a:c):(b>c?b:c);
12 }
13 int main()
14 {
15 int n,x,t,T;
16 while(~scanf("%d",&n))
17 {
18 if(n==0) break;
19 T=0;
20 memset(dp,0,sizeof(dp));
21 for(int i=1;i<=n;i++)
22 {
23 scanf("%d%d",&x,&t);
24 dp[t][x]++;
25 if(T<t) T=t;//时间不一定递增的,找到最大的时间
26 }
27 for(int i=T;i>=0;i--)//从底往上一层一层的加
28 {
29 for(int j=0;j<=10;j++)
30 {
31 if(j==0) dp[i][j]+=max1(dp[i+1][0],dp[i+1][1]);
32 else if(j==10) dp[i][j]+=max1(dp[i+1][9],dp[i+1][10]);
33 else dp[i][j]+=max2(dp[i+1][j+1],dp[i+1][j],dp[i+1][j-1]);
34 }
35 }
36 printf("%d
", dp[0][5]);//起始位置在5
37 }
38 return 0;
39 }
View Code
HDOJ 4540 威威猫系列故事--打地鼠
http://acm.hdu.edu.cn/showproblem.php?pid=4540
也是数塔,从上往下,从下往上都可以,只不过每次是在下面一层中选最优的
1 #include<cstdio>
2 #include<cstring>
3 int n,k,a[25][15],dp[25][15];
4 int abss(int a)
5 {
6 return a>0?a:-a;
7 }
8 int main()
9 {
10 while(scanf("%d%d",&n,&k)!=EOF)
11 {
12 for(int i=1;i<=n;i++)
13 {
14 for(int j=1;j<=k;j++)
15 {
16 scanf("%d",&a[i][j]);//第i秒第j个位置有老鼠
17 }
18 }
19 memset(dp,0,sizeof(dp));
20 int tmp,cur,ans=1000000;
21 for(int i=n-1;i>=1;i--)//从下往上选最优
22 {
23 for(int j=1;j<=k;j++)
24 {
25 tmp=1000000;
26 for(int m=1;m<=k;m++)
27 {
28 cur=abss(a[i][j]-a[i+1][m])+dp[i+1][m];
29 if(cur<tmp)
30 {
31 tmp=cur;
32 }
33 }
34 dp[i][j]+=tmp;
35 }
36 }
37 for(int i=1;i<=k;i++)//最后在第一层中选出最小的
38 {
39 if(dp[1][i]<ans)
40 {
41 ans=dp[1][i];
42 }
43 }
44 printf("%d
", ans);
45 }
46 return 0;
47 }
View Code
HDOJ 1087 Super Jumping!
http://acm.hdu.edu.cn/showproblem.php?pid=1087
各项和最大的LIS
1 #include<cstdio>
2 #define MAXN 1010
3 #define LL long long
4 LL a[MAXN],dp[MAXN],ans;
5 int n;
6 int main()
7 {
8 while(scanf("%d",&n)!=EOF)
9 {
10 if(n==0) break;
11 for(int i=0;i<n;i++)
12 {
13 scanf("%lld",&a[i]);
14 }
15 for(int i=0;i<n;i++)
16 {
17 dp[i]=a[i];//dp[i]保存的是到i为止满足题意的和的最大值
18 }
19 for(int i=0;i<n;i++)
20 {
21 ans=0;
22 for(int j=0;j<i;j++)//在i前面找到一个满足题意的且和最大的
23 {
24 if(a[i]>a[j]&&dp[j]>ans)
25 {
26 ans=dp[j];
27 }
28 }
29 dp[i]+=ans;
30 }
31 ans=0;
32 for(int i=0;i<n;i++)
33 {
34 if(dp[i]>ans)
35 ans=dp[i];
36 }
37 printf("%lld
", ans);
38 }
39 return 0;
40 }
View Code
HDOJ 1160 FatMouse's speed
http://acm.hdu.edu.cn/showproblem.php?pid=1160
类似LIS,要输出序列,这份代码写的比较搓...
1 #include<cstdio>
2 #include<algorithm>
3 #define MAXN 1010
4 using namespace std;
5 struct mouse
6 {
7 int w,s,no,l,pre;//重量、速度、编号、以此老鼠为结尾的满足题意序列的最长长度、在满足题意序列中的前驱(用于输出路径)
8 };
9 mouse mice[MAXN],tmp;
10 bool cmp(mouse a,mouse b)
11 {
12 if(a.w==b.w) return a.s>b.s;
13 return a.w<b.w;
14 }
15 bool cmp2(mouse a,mouse b)
16 {
17 return a.no<b.no;
18 }
19 int main()
20 {
21 int tot=0,cur,k;
22 while(scanf("%d%d",&tmp.w,&tmp.s)!=EOF)
23 {
24 tmp.no=++tot;
25 tmp.l=1;
26 tmp.pre=tot;
27 mice[tot]=tmp;
28 }
29 sort(mice+1,mice+tot+1,cmp);
30 for(int i=1;i<=tot;i++)
31 {
32 cur=0; k=mice[i].no;
33 for(int j=1;j<i;j++)
34 {
35 if(mice[j].w<mice[i].w&&mice[j].s>mice[i].s&&mice[j].l>cur)
36 {
37 cur=mice[j].l;
38 k=mice[j].no;
39 }
40 }
41 mice[i].l+=cur;
42 mice[i].pre=k;
43 }
44 cur=0;k=0;
45 for(int i=1;i<=tot;i++)
46 {
47 if(mice[i].l>cur)
48 {
49 cur=mice[i].l;
50 k=mice[i].no;
51 }
52 }
53 sort(mice+1,mice+tot+1,cmp2);
54 printf("%d
", cur);
55 tmp=mice[k];
56 int top=-1,print[MAXN];
57 for(int i=1;i<=cur;i++)//最后拿个栈输出的
58 {
59 print[++top]=tmp.no;
60 tmp=mice[tmp.pre];
61 }
62 while(top>-1)
63 {
64 printf("%d
",print[top--]);
65 }
66
67 }
View Code
HDOJ 1159 Common Subsequence
http://acm.hdu.edu.cn/showproblem.php?pid=1159
LCS 经典DP
1 #include<cstdio>
2 #include<cstring>
3 #define MAXN 1005
4 char str1[MAXN],str2[MAXN];
5 int dp[MAXN][MAXN];
6 int mmax(int a,int b)
7 {
8 return a>b?a:b;
9 }
10 int main()
11 {
12 while(~scanf("%s",str1))
13 {
14 scanf("%s",str2);
15 memset(dp,0,sizeof(dp));
16 int n=strlen(str1);
17 int m=strlen(str2);
18 for(int i=1;i<=n;i++)//按着状态转移方程写就行了,也没什么细节...
19 {
20 for(int j=1;j<=m;j++)
21 {
22 if(str1[i-1]==str2[j-1])
23 {
24 dp[i][j]=dp[i-1][j-1]+1;
25 }else
26 {
27 dp[i][j]=mmax(dp[i-1][j],dp[i][j-1]);
28 }
29 }
30 }
31 printf("%d
", dp[n][m]);
32 }
33 return 0;
34 }
View Code
HDOJ 1423 Greatest Common Increasing Subsequence
http://acm.hdu.edu.cn/showproblem.php?pid=1423
LCIS 网上方法也很多了 这里贴个O(n^2)的...具体详细解释请看代码注释中的模拟过程...
1 #include<cstdio>
2 #include<cstring>
3 #define MAXN 510
4 #define REP(i,a,b) for(int i=a;i<b;i++)
5 int a[MAXN],b[MAXN],dp[MAXN],n,m,T,max;
6 int main()
7 {
8 scanf("%d",&T);
9 while(T--)
10 {
11 scanf("%d",&n);
12 REP(i,0,n) scanf("%d",&a[i]);
13 scanf("%d",&m);
14 REP(i,0,m) scanf("%d",&b[i]);
15 memset(dp,0,sizeof(dp));
16 /*看不懂的建议自己先动手模拟一遍
17 表面上dp[]是一维的,其实它代表的是dp[i,j]
18 1 4 2 6 3 8 5 9 1
19 2 7 6 3 5 1
20 比如上面这两个序列:
21 i=0:把dp[5]置为1,因为有相等的
22 i=1:虽然在b[5]时,max=1了,但是b后面并没有4了,所以也没有更新
23 i=2:把dp[0]置为1
24 i=3:这一步比较关键了,理解了就懂这个算法了 a[3]=6
25 j=0时,把max更新为1,这代表在6之前a里面已经有一个2与b里面的匹配了
26 所以此时的max=1,如果在b里面2的后面还能找到一个6,那么就把dp[2]置为2
27 因为起码有个2 6是公共上升子序列了
28 i=4......后面的一步步模拟 到i=6即a[6]=5的时候是最大的3 把dp[4]置为3
29 ...最后遍历一遍dp数组找到最大的值即为所求
30 */
31 REP(i,0,n) {
32 max=0;
33 REP(j,0,m) {
34 if(a[i]>b[j]&&dp[j]>max) max=dp[j];
35 if(a[i]==b[j]) dp[j]=max+1;
36 }
37 }
38 max=0;
39 REP(i,0,m) if(dp[i]>max) max=dp[i];
40 printf("%d
",max);
41 if(T) printf("
");
42 }
43 return 0;
44 }
View Code
COJ 1120 病毒
http://122.207.68.93/OnlineJudge/problem.php?id=1120
第八届湖南省赛的题目 裸的LCIS...
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 const int maxn=1001;
6 int a[maxn],b[maxn],dp[maxn];
7 int n,m;
8 int LICS()
9 {
10 int MAX,i,j;
11 memset(dp,0,sizeof(dp));
12 for(i=0;i<n;i++)
13 {
14 MAX=0;
15 for(j=0;j<m;j++)
16 {
17 if(a[i]>b[j] && MAX<dp[j])
18 MAX=dp[j];
19 if(a[i]==b[j])
20 dp[j]=MAX+1;
21 }
22 }
23 MAX=0;
24 for(i=0;i<m;i++)
25 if(dp[i]>MAX)
26 MAX=dp[i];
27 return MAX;
28 }
29 int main()
30 {
31 int t,i;
32 scanf("%d",&t);
33 while(t--)
34 {
35 scanf("%d",&n);
36 for(i=0;i<n;i++)
37 scanf("%d",&a[i]);
38 scanf("%d",&m);
39 for(i=0;i<m;i++)
40 scanf("%d",&b[i]);
41 printf("%d
",LICS());
42 }
43 return 0;
44 }#include <iostream>
45 #include <cstdio>
46 #include <cstring>
47 using namespace std;
48 const int maxn=1001;
49 int a[maxn],b[maxn],dp[maxn];
50 int n,m;
51 int LICS()
52 {
53 int MAX,i,j;
54 memset(dp,0,sizeof(dp));
55 for(i=0;i<n;i++)
56 {
57 MAX=0;
58 for(j=0;j<m;j++)
59 {
60 if(a[i]>b[j] && MAX<dp[j])
61 MAX=dp[j];
62 if(a[i]==b[j])
63 dp[j]=MAX+1;
64 }
65 }
66 MAX=0;
67 for(i=0;i<m;i++)
68 if(dp[i]>MAX)
69 MAX=dp[i];
70 return MAX;
71 }
72 int main()
73 {
74 int t,i;
75 scanf("%d",&t);
76 while(t--)
77 {
78 scanf("%d",&n);
79 for(i=0;i<n;i++)
80 scanf("%d",&a[i]);
81 scanf("%d",&m);
82 for(i=0;i<m;i++)
83 scanf("%d",&b[i]);
84 printf("%d
",LICS());
85 }
86 return 0;
87 }
View Code
HDOJ 1257 最少拦截系统
http://acm.hdu.edu.cn/showproblem.php?pid=1257
平常的导弹题是求最多拦多少导弹,就是求出一个最长的不增子序列...
这题问至少要安装多少套系统,其实就是找出最长的严格递增子序列的长度,即LIS
好像有个定理是证这个的,不过手写一个序列模拟一下也能看出来...
给出两个版本吧...一个O(n^2)的 一个O(nlogn)的...具体看代码注释
1 #include<cstdio>
2 #include<cstring>
3 #define MAXN 1005
4 int a[MAXN],dp[MAXN],n,max;//这个dp[i]存的是以i为结尾的最长递增子序列的长度
5 int main()
6 {
7 while(scanf("%d",&n)!=EOF)
8 {
9 for(int i=0;i<n;i++) scanf("%d",&a[i]);
10 memset(dp,0,sizeof(dp));
11 for(int i=0;i<n;i++)
12 {
13 max=0;
14 for(int j=0;j<i;j++)//转移方程dp[i]=max{dp[j]+1} 其中j要满足的a[i]>a[j]
15 {
16 if(a[i]>a[j]&&dp[j]>max) max=dp[j];//因为要找到这个最大值 所以从0到i遍历了一遍
17 }
18 dp[i]=max+1;
19 }
20 for(int i=0;i<n;i++) max=max>dp[i]?max:dp[i];
21 printf("%d
",max);
22 }
23 return 0;
24 }
View Code
1 #include<cstdio>
2 #include<cstring>
3 #define MAXN 1005
4 int a[MAXN],dp[MAXN],n;
5 /*
6 这个版本的dp[i]存的就是a中长度为i的递增子序列末尾数的最小值
7 比较绕口 给个序列吧:2 1 4 3 5 数组下标从1开始
8 a[1]=2 dp[1]=2
9 a[2]=1 dp[1]=1
10 a[3]=4 dp[2]=4
11 a[4]=3 dp[2]=3
12 a[5]=5 dp[3]=5
13 最终dp更新到第几项 最长长度就是几 而不是dp里面存的数
14 更详细的模拟过程可以看这个
15 http://www.cnblogs.com/mengxm-lincf/archive/2011/07/12/2104745.html
16 二分部分的代码借鉴了这个
17 http://www.wutianqi.com/?p=1850
18 */
19 int BSearch(int x,int k)
20 {
21 int low=1,high=k,mid;
22 while(low<=high)
23 {
24 mid=(low+high)>>1;
25 if(x>=dp[mid]) low=mid+1;
26 else high=mid-1;
27 }
28 return low;
29 }
30 int main()
31 {
32 while(scanf("%d",&n)!=EOF)
33 {
34 for(int i=1;i<=n;i++) scanf("%d",&a[i]);
35 memset(dp,0,sizeof(dp));
36 int k=1; dp[k]=a[1];
37 for(int i=2;i<=n;i++)
38 {
39 if(a[i]>dp[k]) dp[++k]=a[i];
40 else dp[BSearch(a[i],k)]=a[i];
41 }
42 printf("%d
",k);
43 }
44 return 0;
45 }
View Code
HDOJ 1025 Constructing Roads In JGShining's Kingdom
http://acm.hdu.edu.cn/showproblem.php?pid=1025
这题也是一个裸的LIS 不过因为n比较大(<=500000) 用n^2的算法妥妥超时(如果出题人没有偷懒的话...)
按照上面写的nlogn的算法写就OK了...
1 #include<cstdio>
2 #include<cstring>
3 #define MAXN 500010
4 #define REP(i,a,b) for(int i=a;i<b;i++)
5 #define MEM(a) memset(a,0,sizeof(a))
6 int a[MAXN],dp[MAXN],n;
7 int BSearch(int x,int k)
8 {
9 int low=1,high=k,mid;
10 while(low<=high)
11 {
12 mid=(low+high)>>1;
13 if(x>=dp[mid]) low=mid+1;
14 else high=mid-1;
15 }
16 return low;
17 }
18 int main()
19 {
20 int cases=0,x,y;
21 while(~scanf("%d",&n))
22 {
23 REP(i,1,n+1) {
24 scanf("%d%d",&x,&y);
25 a[x]=y;
26 }
27 MEM(dp);
28 int k=1; dp[k]=a[1];
29 REP(i,2,n+1) {
30 if(a[i]>dp[k]) dp[++k]=a[i];
31 else dp[BSearch(a[i],k)]=a[i];
32 }
33 printf("Case %d:
",++cases);
34 printf("My king, at most %d road", k);//坑爹啊 road roads傻傻分不清楚
35 if(k!=1) printf("s");
36 printf(" can be built.
");
37 }
38 return 0;
39 }
View Code
HDOJ 2602 Bone Collector
http://acm.hdu.edu.cn/showproblem.php?pid=2602
01背包 经典动规 给出两种方法吧 一种空间二维的 一种空间一维的
1 #include<cstdio>
2 #include<cstring>
3 #define MAXN 1005
4 int n,v,c[MAXN],w[MAXN],f[MAXN][MAXN];
5 int mmax(int a,int b)
6 {
7 return a>b?a:b;
8 }
9 int main()
10 {
11 int T;
12 scanf("%d",&T);
13 while(T--)
14 {
15 scanf("%d%d",&n,&v);
16 for(int i=1;i<=n;i++)
17 {
18 scanf("%d",&w[i]);
19 }
20 for(int i=1;i<=n;i++)
21 {
22 scanf("%d",&c[i]);
23 }
24 memset(f,0,sizeof(f));
25 for(int i=1;i<=n;i++)//经典动规 f[i][j]表示把i件物品放入容量为j的背包中能获得的最大价值
26 {
27 for(int j=0;j<=v;j++)//这里j要从0开始,从1开始就WA,这一点我到现在也没理解,各位大神谁看到了给我解释一下...
28 {
29 if(j>=c[i]) f[i][j]=mmax(f[i-1][j],f[i-1][j-c[i]]+w[i]);//按照转移方程写就OK了
30 else f[i][j]=f[i-1][j];
31 }
32 }
33 printf("%d
", f[n][v]);
34 }
35 return 0;
36 }
View Code
这种一维的比较难理解一点,具体解释全在注释里了...
1 #include<cstdio>
2 #include<cstring>
3 #define MAXN 1005
4 int n,v,c[MAXN],w[MAXN],f[MAXN];
5 int mmax(int a,int b)
6 {
7 return a>b?a:b;
8 }
9 int main()
10 {
11 int T;
12 scanf("%d",&T);
13 while(T--)
14 {
15 scanf("%d%d",&n,&v);
16 for(int i=1;i<=n;i++)
17 {
18 scanf("%d",&w[i]);
19 }
20 for(int i=1;i<=n;i++)
21 {
22 scanf("%d",&c[i]);
23 }
24 memset(f,0,sizeof(f));
25 /*
26 状态转移方程是f[j]=max(f[j],f[j-c[i]]+w[i]) 代表背包容量为j的最大价值
27 这里f是一维的,但是其实后面max里面的f[j]表示的是f[i-1,j],要做到这一点需要以j从v到0的逆序方式遍历
28 具体怎么理解呢,其实自己模拟一遍是最好的...
29 我们知道,实质上01背包问题的状态转移方程是f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i])
30 前面是不放第i件物品的策略,后面是放第i件物品的策略 但是要选择放策略的时候
31 需要的f[i-1][j-c[i]]这个值必须是没有放第i件物品计算出来的值,否则就不是01背包了,
32 因为每件物品你都可能放了多件
33 只有让j从v到0的遍历方式,才能保证在计算f[j]时用到的f[j-c[i]]是第i-1次的(即没有放第i件物品的)
34 比如c[i] 1 2 3 4 5//代价
35 w[i] 5 4 3 2 1//价值
36 如果j是从0到v的顺序遍历的,则算出来的dp[1]=5 在你算dp[2]的时候,此时调用的
37 dp[j]=max(dp[j],dp[j-c[i]]+w[i]) 你会得到dp[2]=dp[2-1]+w[1]=10
38 这个结果意味着容量为2的背包最大价值是10,而在01背包中这个值显然应该是4,原因就在于由于顺序遍历
39 造成了在计算dp[2]时,放了两件第1件物品 这在01背包中是不允许的
40 而采用逆序的方式则可以保证在计算dp[2]的时候,dp[1]还是0(在背包不要求装满的情况下,只要给dp初始化0就行)
41 这样就能保证每个物品至多放一次 自己按照逆序模拟一遍就能体会到这个策略的正确性了
42 ps:这里多说一句吧,其实按照j从0到v的方式遍历,刚好是另一种背包问题--完全背包的解法,这种背包问题中,
43 每个物品都有无限件可选,也就是上面的计算dp[2]得到10才是正确的
44 这种策略正确的原因就在于,完全背包问题实质上的转移方程是:
45 f[i][j]=max(f[i-1][j],f[i][j-c[i]]+w[i])--也分为两种策略 不放、放,但是放的话可以放无限件
46 细细体会吧...
47 更多背包问题的资料,请参考《背包九讲》...
48 */
49 for(int i=1;i<=n;i++)
50 {
51 for(int j=v;j>=c[i];j--)
52 {
53 f[j]=mmax(f[j],f[j-c[i]]+w[i]);
54 }
55 }
56 printf("%d
", f[v]);
57 }
58 return 0;
59 }
View Code
HDOJ 4512 吉哥系列故事——完美队形I
http://acm.hdu.edu.cn/showproblem.php?pid=4512
这题出的比较巧妙,可以另搞一个数组是原数组的逆序,然后求LCIS
对于中间点,是奇数时,简单判断一下是否用到了中间点,最后结果是2*k-1 否则就是2*k
具体见代码:
1 #include<cstdio>
2 #include<cstring>
3 using namespace std;
4 int n,ans,a[201],dp[201];
5 inline void Max(int &a,const int b){if(b>a) a=b;}
6 int main()
7 {
8 int T;
9 scanf("%d",&T);
10 while(T--){
11 scanf("%d",&n);
12 memset(dp,0,sizeof dp);
13 for(int i=0;i<n;i++) scanf("%d",a+i);
14 ans=0;
15 for(int k=n-1;k>=0;k--){
16 int x=a[k],mx=0;
17 for(int i=0;i<=k;i++){
18 if(a[i]<x) Max(mx,dp[i]);
19 else if(a[i]==x) dp[i]=mx+1;
20 if(i<k) Max(ans,dp[i]*2);
21 else Max(ans,dp[i]*2-1);
22 }
23 }
24 printf("%d
",ans);
25 }
26 return 0;
27 }
View Code
持续更新中...