首页 > 代码库 > dp考试
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 }
dp考试