dp考试
a 【问题描述】 ?个物品 ，每个物品都有恰好两。第 ?种物品的体积和价值分别是 ??和??。 背包的体积为 ?，问在不超过背包体积的情况下最多能放进少价值物品。 ，问在不超过背包体积的情况下最多能放进少价值物品。 ，问在不超过背包体积的情况下最多能放进少价值物品。 ，问在不超过背包体积的情况下最多能放进少价值物品。 ，问在不超过背包体积的情况下最多能放进少价值物品。 ，问在不超过背包体积的情况下最多能放进少价值物品。 ，问在不超过背包体积的情况下最多能放进少价值物品。 【输入格式】 第一行 两个整数 ?,?。 接下来 ?行每两个整数 ??,??。 【输出格式】 一行个整数代表答案 。
【样例输入】 2 3 1 2 2 1 【样例输出】 4 【数据规模与约定】 对于 100%的数据， 1≤?,?,??,??≤100,。
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<cmath>
5 using namespace std;
6 const int MAXN=101;
7 int w[101],v[101];
8 int f[101][101];
9 int main()
10 {
11 int n,m;
12 scanf("%d%d",&n,&m);
13 for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);
14 for(int i=1;i<=n;i++)
15 {
16 for(int j=0;j<=m;j++)// 背包的容量
17 {
18 for(int k=0;k<=2;k++)
19 {
20 if(j>=w[i]*k)
21 f[i][j]=max(f[i][j],f[i-1][j-w[i]*k]+v[i]*k);
22 else break;
23 }
24 }
25 }
26 printf("%d",f[n][m]);
27 return 0;
28 }b 【问题描述】 给你 ?个数 ，找出 这?个数的最长 上升 子序列 。即对于 数列 ?1,?2,⋯,??，找 到一组 ?1,?2,⋯,??使得 ?1<?2<⋯<??且??1<??2<⋯<???，同时 使得 这个 ?最大 ，求最大 的?。 【输入格式】 第一行是 一个正整数 ?。 接下来 一行 ?个正整数 ?1,?2,⋯,?_?。 【输出格式】 输出 最大 的?。 【样例输入】 4 4 2 3 1 54 2 3 1 54 2 3 1 54 2 3 1 54 2 3 1 54 2 3 1 54 2 3 1 54 2 3 1 54
【样例输出】 3 【数据规模与约定】 100%的数据满足 1≤?,??≤1000。
考场上现推的，，，好佩服自己。。。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 int dp[1001][1001];
7 int main()
8 {
9 int n;
10 scanf("%d",&n);
11 for(int i=1;i<=n;i++)
12 scanf("%d",&dp[i][1]);// 第i个数，长度为1的上升序列是自己
13 for(int i=1;i<=n;i++)//每个数
14 {
15 for(int k=1;k<=i;k++)//之前的每个数
16 {
17 for(int j=1;j<=i;j++)//最长上升
18 {
19 if(dp[i][1]>dp[k][j])
20 {
21 if(dp[k][j+1]!=0)
22 dp[k][j+1]=min(dp[k][j+1],dp[i][1]);
23 else dp[k][j+1]=dp[i][1];
24 }
25 else break;
26 }
27 }
28
29 }
30 int ans=0;
31 for(int i=1;i<=n;i++)
32 {
33 for(int j=1;j<=1001;j++)
34 {
35 if(dp[i][j]==0)
36 {
37 if(j>ans)
38 ans=j;
39 break;
40 }
41 }
42 }
43 printf("%d",ans-1);
44 return 0;
45 }c 【问题描述】 一个 字符串 的子序列 是指从中 挑选出 任意 位置 的字符 之后 再组成 的 字符串 。 如果 对于 abcde，ace、ad、bc、bde都是 其子序列 。现在 给你 两个 字符串 ，求一 个字符串 ，使得 该字符串 是这两个 字符串 的子序列 且该字符串 长度 最长 。 【输入格式】 第一行个 字符串 ，只包含 小写 字母 。 第二行 一个 字符串 ，只包含 小写字母 。 【输出格式】 一行 一个 整数 ，代表 字符串 长度 。 【样例输入】 abcdebcdebcdebcde bedcabedcabedcabedcabedca
【样例输出】 2 【数据规模与约定】 对于 100%的数据 ，字符串 长度 不超过 500。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 const int MAXN=601;
7 char a[MAXN],b[MAXN];
8 int dp[MAXN][MAXN];
9 int main()
10 {
11 scanf("%s %s",a,b);
12 int la=strlen(a),lb=strlen(b);
13 for(int i=0;i<la;i++)
14 {
15 for(int j=0;j<lb;j++)
16 {
17 dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
18 if(a[i]==b[j])
19 dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
20 }
21 }
22 printf("%d\n",dp[la-1][lb-1]);
23 return 0;
24 }