牛客网算法竞赛入门课练习题单6+其他dp题
拦截导弹
https://ac.nowcoder.com/acm/problem/16810
拦截导弹 https://ac.nowcoder.com/acm/problem/16810
涉及算法：最长递增子序列(LIS)。dp[i]表示以第i个元素结尾的最长递增子序列的长度。数组中每个元素对于本身可以构成一个递增序列，所有初始化dp为1，然后循环取判断每个元素与在它之前的元素比较，前面的元素小于它，则说明可以放在该元素后面，然后再判断dp[i]与dp[j] + 1的大小，如果小于他没必要放在这个元素后面，这样也就可以求出最大值来。最长不递增子序列也是同样的道理。
分析：最长不递增的序列个数等于最长递增序列，先用一个dp算出最长不递增序列的长度，类似的可以算出最长递增序列的长度。
#include <bits/stdc++.h>
#include <iostream>
const int Max = 100 * 100 * 100 + 5;
#define LL long long
const int mod = 1e9+7;
//const int inx = INT_MAX;
using namespace std;
// srand(time(NULL));
// m = rand() % 1000 + 1;
//定义i i(A) i+n i+n(B) i+n+n i+n+n(C)
//bitset<Max>s,q;
int dp1[100005];
int dp2[100005];
int a[100005];
int main()
{
int i,j,n,t;
int x,ans = 0,ans1 = 0;
t = 0;
while(cin >> x){
a[++t] = x;
}
for(i = 1; i <= t; i++) dp1[i] = 1,dp2[i] = 1;
for(i = 1; i <= t; i++){
for(j = 1; j < i; j++){
if(a[i] <= a[j] && dp1[i] <= dp1[j] + 1){
dp1[i] = dp1[j] + 1;
}
}
ans = max(ans,dp1[i]);
}
cout << ans << endl;
for(i = 1; i <= t; i++){
for(j = 1; j < i; j++){
if(a[i] > a[j] && dp2[i] < dp2[j] + 1){
dp2[i] = dp2[j] + 1;
}
}
ans1 = max(ans1,dp2[i]);
}
cout << ans1;
return 0;
}
被3整除的子序列
https://ac.nowcoder.com/acm/problem/21302
思路(个人理解)：
1：一个数能够被3整除说明这个数所有位上的数之和为3的倍数，那么我们就去对每位上的数求和，对3取模，我们会的到0,1,2,取模为0的就是我们要的答案，现在就是要找到有多少个序列取模为零。
2：考虑dp[i][j],表示0-i组成的子序列中，数模3位j的个数有多少个，然后考虑转移方程，dp[i][j]可以有前i-1个转移过来，考虑第i个数字加不加上去，若不加上去则dp[i][j] = dp[i-1][j],也就是前i个数组成的子序列中，数模3位j的个数有多少个，和i-1一样，若加上去，则dp[i][j] = dp[i-1][(j-m+3)%3](m=a[i]%3),也就是前i-1个数组成的序列取模后的数加上m后取模的数有多少个。**还有dp[i][m] += 1,自己也可以是一个序列**。
3：综合**dp[i][j] = (dp[i-1][j]+dp[i-1][(j-m+3)%3]) % mod,dp[i][m] += 1**.
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
using namespace std;
//781
LL dp[55][3];//dp[i][j]表示前i个数中所有子序列和取模为j的个数
int main()
{
char s[55];
int len;
cin >> s;
len = strlen(s);
for(int i = 0; i < len; i++){
int temp;
temp = (s[i] - '0') % 3;
for(int j = 0; j <= 2; j++){
dp[i][j] = (dp[i - 1][j] + dp[i - 1][(j - temp + 3) % 3]) % mod;
}
dp[i][temp] = (dp[i][temp] + 1) % mod;
}
cout << dp[len - 1][0];
return 0;
}
牛牛与数组
思路：1:动态规划先找状态，再找初始值，然后状态转移，最后确定答案。
2:这道题给了我们数组的限制长度，那么我们可以由更短的数组长度来推到更长的数组长度，考虑数组长度减一满足条件的有多少组。给出状态dp[i][j]表示数组长度为i以数j结尾的满足条件的有多少个。
3:状态转移：dp[i][j] = dp[i-1][m](1<=m<=j&&j%m!=0),然后去枚举，但是我们发现枚举时间复杂度为O（k*k），不能过。
4:考虑dp优化，条件1<=m<=j&&j%m!=0，那我们就去枚举长度为i-1的数组以j的倍数结尾的有多少个，减去就可以了，总体时间复杂的为：O(n*k*sqrt(k))。
超时代码O（n*k*k）：
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
using namespace std;
//781
int dp[10][100005];//dp[i][j]表示长度为i的数中以j结尾的数组个数
int main()
{
int n,k;
cin >> n >> k;
for(int i = 1; i <= k; i++) dp[1][i] = 1;
for(int i = 2; i <= n; i++){
LL sum = 0,sum1;
for(int j = 1; j <= k; j++){
//sum = (sum + dp[i - 1][j]) % mod;//表示长度为i-1的数中以j结尾的数组个数
for(int p = 1; p <= k; p++){
if(p <= j || (p % j) != 0){
dp[i][j] = (dp[i][j] + dp[i - 1][p]) % mod;
}
}
}
}
LL cnt = 0;
for(int i = 1; i <= k; i++){
cnt = (cnt + dp[n][i]) % mod;
}
cout << cnt;
return 0;
} #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
using namespace std;
//781
int dp[15][100005];//dp[i][j]表示长度为i的数中以j结尾的数组个数
int main()
{
int n,k;
cin >> n >> k;
for(int i = 1; i <= k; i++) dp[1][i] = 1;
for(int i = 2; i <= n; i++){
LL sum = 0,sum1;
for(int j = 1; j <= k; j++){
sum = (sum + dp[i - 1][j]) % mod;//表示长度为i-1的数中以j结尾的数组个数
}
for(int j = 1; j <= k; j++){
sum1 = 0;
for(int p = j+j; p <= k; p += j){
sum1 = (sum1 + dp[i - 1][p]) % mod;//计算长度为i-1的数中以j的倍数结尾的数组个数
}
dp[i][j] = (sum - sum1) % mod;
}
}
LL cnt = 0;
for(int i = 1; i <= k; i++){
cnt = (cnt + dp[n][i]) % mod;
}
cout << cnt;
return 0;
} 摆花
思路：
1：题目说了花的种类顺序是按序号从小到大排的，所有我们从前往后推。
2：状态 dp[i][j]:表示前i种花摆j盆花出来的方案数。
3: 转移方程：dp[i][j] = dp[i-1][j](不摆第i种花）dp[i][j] = dp[i-1][j-1]+...+dp[i-1][j-a[i]](摆第i种花，第i种花的数量是1-a[i])。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e6+7;
const LL INF = 1e18;
using namespace std;
//781
LL dp[505][505];//dp[i][j]表示前i种花摆j盆的方案数。
int a[505];
//dp[i][j] = dp[i-1][j] + dp[i-1][j-1]+...+dp[i-1][j-a[i]];
int main()
{
int n,m;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
//for(int i = 0; i <= n; i++) dp[i][0] = 1;
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++){
for(int k = 0; k <= a[i] && k <= j; k++){
dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % mod;
}
}
}
cout << dp[n][m] << endl;
return 0;
} Training Plan
思路：dp[i][j]：表示第i天刷j道题的最小难度。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
const LL INF = 1e18;
using namespace std;
//781
LL dp[505][505];//dp[i][j]表示第i天刷j道题的最小难度。
LL a[505];
int main()
{
int t,n,m;
cin >> t;
while(t--){
cin >> n >> m;
memset(a,0,sizeof(a));
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a+1,a+n+1);
for(int i = 1; i <= n; i++) dp[1][i] = (a[i] - a[1]) * (a[i] - a[1]);
for(int i = 2; i <= m; i++){
for(int j = 1; j <= n; j++){
dp[i][j] = INF;
for(int k = 1; k < j; k++){
dp[i][j] = min(dp[i][j],dp[i-1][k] + (a[j]-a[k+1])*(a[j]-a[k+1]));
}
}
}
LL ans = INF;
for(int i = 0; i <= n; i++){
ans = min(dp[m][i],ans);
}
cout << dp[m][n] << endl;
}
return 0;
}
购物
思路：
1:状态dp[i][j]表示前i天买j个糖果的最少钱。
2:对于每一天要买的糖果我们优先买价格少的，因为要买k个，所有我们提前算出每天糖果价钱的前缀和sum[i][j].
3:转移方程：dp[i][j] = min(dp[i][j],dp[i-1][j-k]+sum[i][k]+k*k).
4:因为要保证每天都有糖果吃，所有到第i天买的所有糖果数必须超过i个，所有到第i天j从i开始枚举到m。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
const int INF = 1e6;
using namespace std;
//781
int dp[505][505];//dp[i][j]表示前i天买j个糖果的最少钱。
int a[505][505];
int sum[505][505];
//dp[i][j] = dp[i-1][j] + dp[i-1][j-1]+...+dp[i-1][j-a[i]];
int main()
{
int n,m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
dp[i][j] = INF;
}
sort(a[i]+1,a[i]+m+1);
for(int j = 1; j <= m; j++) sum[i][j] = sum[i][j-1] + a[i][j];
}
memset(dp,1e6,sizeof(dp));
dp[0][0] = 0;
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
for(int k = 0; k <= j && k <= m; k++){
dp[i][j] = min(dp[i][j],dp[i-1][j-k]+sum[i][k]+k*k);
}
}
}
cout << dp[n][n] << endl;
return 0;
}
取数游戏
思路1：
1：状态dp[i][j][0/1]:表示前i次有j次是取左端的数，然后第i次是取左端/右端的(0/1)
2：转移方程
if(j) dp[i][j][1] = max(dp[i][j][1],max(dp[i-1][j-1][1],dp[i-1][j-1][0])+a[j]*b[i]); dp[i][j][0] = max(dp[i][j][0],max(dp[i-1][j][0], dp[i-1][j][1]) + b[i]*a[n-i+j+1]);思路2：
1：状态：dp[i][j]表示区间i-j的最优解
2：转移方程：dp[i][j] = max(dp[i+1][j]+a[i]*b[k],dp[i][j-1]+a[j]*b[k])
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
const int INF = 1e6;
using namespace std;
//781
int dp[1005][1005][2];//dp[i][j][0/1]1表示选了i个数中j个是左端点，0是右端点。
int a[1005],b[1005];
int main()
{
int t,n;
cin >> t;
while(t--){
cin >> n;
memset(dp,0,sizeof(dp));
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++){
for(int j = 0; j <= i; j++){
if(j) dp[i][j][1] = max(dp[i][j][1],max(dp[i-1][j-1][1],dp[i-1][j-1][0])+a[j]*b[i]);
dp[i][j][0] = max(dp[i][j][0],max(dp[i-1][j][0], dp[i-1][j][1]) + b[i]*a[n-i+j+1]);
}
}
int Max = 0;
for(int i = 0; i <= n; i++){
Max = max(Max,dp[n][i][1]);
Max = max(Max,dp[n][i][0]);
}
cout << Max << endl;
}
return 0;
} 矩阵快速幂：
https://ac.nowcoder.com/acm/contest/1168/K
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define ll long long
#define inf 0x3f3f3f3f
const int mod = 666666;
using namespace std;
struct matrix{
ll m[2][2];
matrix(){
memset(m,0,sizeof(m));
};
};
matrix cf(matrix a,matrix b)
{
matrix temp;
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
for(int k = 0; k < 2; k++){
temp.m[i][j] = (temp.m[i][j] + a.m[i][k]*b.m[k][j]) % mod;
}
}
}
return temp;
}
matrix qpow(matrix a,int n)
{
matrix res;
for(int i = 0; i < 2; i++) res.m[i][i] = 1;
while(n){
if(n & 1) res = cf(res,a);
a = cf(a,a);
n >>= 1;
}
return res;
}
int main()
{
ll n,m;
matrix a;
while(cin >> n >> m){
a.m[0][0] = 4;
a.m[0][1] = 3;
a.m[1][0] = 1;
a.m[1][1] = 0;
ll ans;
a = qpow(a,n - 2);
ans = (a.m[0][0]*233 % mod + a.m[0][1]*4 % mod) % mod;
ans = m - ans;
cout << ans << endl;
}
return 0;
} 最大子矩阵和：
先看一维的：核心代码dp[i] = max(dp[i - 1] + a[i],a[i]),dp[i]表示以第i个元素结尾的子矩阵的最大和。
//这样写方便找出最大值
int getmax(int a[],int n)
{
int i,s = 0,m = a[0];
for(i = 0; i < n; i++)
{
if(s >= 0) s += a[i];
else s = a[i];
if(s > m) m = s;
}
return m;
} 二维：我们可以先把二维的转化成一维的再按一维求最大子矩阵和，如何转化，我们可以通过行或列的压缩，我们按行压缩，将多行压缩成一行。 如：
1 -1 2
4 9 15
-7 1 10
4 9 15
-7 1 10
取第一行：1 -1 2 m = 2
再加上第二行： 5 8 17 m = 30
再加上第三行： -2 9 27 m = 34
取第二行： 4 9 15 m = 28
...
这样可以把所有能构成的子矩阵全部搞出来。
代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int getmax(int a[],int n)
{
int i,s = 0,m = a[0];
for(i = 0; i < n; i++)
{
if(s >= 0) s += a[i];
else s = a[i];
if(s > m) m = s;
}
return m;
}
int main()
{
int N;
while(~scanf("%d",&N))
{
int i,j,k;
int sum[105];
int a[105][105];
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
scanf("%d",&a[i][j]);
int n = a[0][0];
for(i = 0; i < N; i++)//先取第i行。
{
memset(sum,0,sizeof(sum));
for(j = i; j < N; j++)//在取了第i行的基础上加上第j行
{
for(k = 0; k < N; k++)
{
sum[k] += a[j][k];
}
int m = getmax(sum,N);
if(m > n) n = m;
}
}
printf("%d\n",n);
}
return 0;
} 数字和为sum的方法数：01背包变形
思路：看题目意思应该相同下标不同顺序算一种。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
ll dp[1005];//dp[i][j]表示前i个数中组成和为j的种类数
int sum,a[1005];
int main()
{
int n;
cin >> n >> sum;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
memset(dp,0,sizeof(dp));
dp[0] = 1;//组成0，即不取一种
for(int i = 1; i <= n; i++){
for(int j = sum; j >= a[i]; j--){
dp[j] = dp[j] + dp[j - a[i]];//和01背包的不同之处，01背包是dp[j] = max(dp[j],dp[j-a[i]);
}
}
cout << dp[sum] << endl;
return 0;
} 宵暗的妖怪
比赛链接：https://ac.nowcoder.com/acm/contest/8755#question
思路：
动规三步：
1）找状态：dp[i][0]表示从下标1开始，并以下标i结尾的区间，不吞噬第i个数的最大饱食度，同理dp[i][1]表示吞噬第i个数的最大饱食度。根据题意可知，如果吞噬了i，那么i-1，i-2也会被吞噬。
2）状态转移：dp[i][0] = max(dp[i-1[0],dp[i-1][0], dp[i][1] = dp[i-2][0]+a[i-1]
3）初始化：我们要从第三个数开始，因为每次要连续吞噬三个，而我们的i表示吞噬的是这三个中的最后一个。如果小于三，那么就是0.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
ll dp[100005][3];
int a[100005];
int main()
{
int n,x;
cin >> n;
cin >> a[1] >> a[2];
for(int i = 3; i <= n; i++){
cin >> a[i];
dp[i][0] = max(dp[i-1][1],dp[i-1][0]);
dp[i][1] = dp[i-2][0]+a[i-1];
}
cout << max(dp[n][1],dp[n][0]) << endl;
return 0;
} 第十届蓝桥杯国赛 B题
题面：
2019可以被分解成若干个两两不同的素数，请问不同的分解方案有多少种？
注意：分解方案不考虑顺序，如2+2017=2019和2017+2=2019属于同一种方案。
注意：分解方案不考虑顺序，如2+2017=2019和2017+2=2019属于同一种方案。
解法同上
这种解法看上去好像会有2+2017，2017+2这种类似的重复，其实是没有的，因为这些素数是从小到大排列好了的，而且是选完前面的在选后面的，所有不会出现这种重复情况。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9;
const ll ds = 1e15+7;
//const double p = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
ll dp[2020];
int prime[2020],vis[2020],cnt = 0;
void getprime()
{
for(int i = 2; i <= 2019; i++){
if(!vis[i]){
vis[i] = i;
prime[cnt++] = i;
}
for(int j = 0; j < cnt; j++){
if(i*prime[j] > 2019) break;
vis[i*prime[j]] = prime[j];
if(i%prime[j] == 0) break;
}
}
}
int main()
{
int n;
getprime();
memset(dp,0,sizeof(dp));
dp[0] = 1;//不取
for(int i = 0; i < cnt; i++){
for(int j = 2019; j >= prime[i]; j--){
dp[j] = dp[j] + dp[j - prime[i]];
}
}
cout << dp[2019] << endl;
return 0;
}
//答案：55965365465060 第十届蓝桥杯国赛 F题：dp
题面：
题目给定两个字符串S和T，保证S的长度不小于T的长度，问至少修改S的多少个字符，可以令T成为S的子序列。
输入描述：
两行。
第一行是字符串S，第二行是字符串T。
保证S的长度不小于T的长度，S的长度范围在10~1000之间。
输出描述：
答案，一个非负整数。
输入样例：
XBBBBBAC
ACC
输出样例：
2
思路：
1）状态：dp[i][j] 表示，使t串前j段中成为s串的前i段的子序列的修改字符次数。
2）初值：初始化当j=0和i=j的情况
3）状态转移：
if (s[i] == t[j]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+1);
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9;
const ll ds = 1e15+7;
//const double p = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
int dp[1005][1005];
int main()
{
int l1,l2;
string s,t;
cin >> s >> t;
l1 = s.size();
l2 = t.size();
// memset(dp,0x3f3f,sizeof(dp));
if(s[0] != t[0]) dp[0][0] = 1;
for(int i = 1; i < l1; i++){
if(s[i] != t[0]) dp[i][0] = dp[i-1][0];
else dp[i][0] = 0;
}
for(int i = 1; i < l2; i++){
if(s[i] != t[i]) dp[i][i] = dp[i-1][i-1]+1;
else dp[i][i] = dp[i-1][i-1];
}
for(int j = 1; j < l2; j++){
for(int i = j+1; i < l1; i++){
// if(i == 0 || j == 0) continue;
if(s[i] == t[j]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = min(dp[i-1][j-1]+1,dp[i-1][j]);
}
}
cout << dp[l1-1][l2-1] << endl;
}
查看9道真题和解析