牛客网算法竞赛入门课练习题单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))。
#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; }
摆花
#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
#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; }
购物
#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; }
取数游戏
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:
#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; }
最大子矩阵和:
//这样写方便找出最大值 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; }二维:我们可以先把二维的转化成一维的再按一维求最大子矩阵和,如何转化,我们可以通过行或列的压缩,我们按行压缩,将多行压缩成一行。
4 9 15
-7 1 10
#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; }
宵暗的妖怪
#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题
注意:分解方案不考虑顺序,如2+2017=2019和2017+2=2019属于同一种方案。
#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
输出样例:
#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; }