洛谷【动态规划2】线性状态动态规划 题解4-8 详细易懂不炫技

开始备战机考其实机考应该没什么问题但是我想提一下自己的上限。至少这是之前励志要填的坑大丈夫岂能......此处省略。T4P4933 大师 - 洛谷我真服了DP这个东西感觉不是人类能想出来的你看得懂想不到。#includeiostream #includecstring #define i64 long long #define mx 20000 #define mod 998244353 using namespace std; i64 n,m,q; i64 ans0; i64 h[40005],g[40005]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinn; for(i64 i1;in;i){ cinh[i]; } ansn; for(i64 d-mx;dmx;d){ if(d0) continue; memset(g,0,sizeof(g)); for(i64 i1;in;i){ i64 needh[i]-d; i64 dpi1; if(need0needmx){ dpi(dpig[need])%mod; } ans(ansdpi-1)%mod; g[h[i]](g[h[i]]dpi)%mod; } } i64 cnt[20005] {0}; for(i64 i1;in;i) cnt[h[i]]; i64 pow2[1005]; pow2[0] 1; for(i64 i1;in;i) pow2[i]pow2[i-1]*2%mod; for(int i0;imx;i){ if(cnt[i]2){ ans(anspow2[cnt[i]]-1-cnt[i])%mod; } } ans(ans%modmod)%mod; coutansendl; return 0; }T5P1874 快速求和 - 洛谷首先这个num数组就不好求吧要用一次dp。lens.length();for(i64 i1;ilen;i){for(i64 ji;jlen;j){num[i][j]num[i][j-1]*10(s[j-1]-0);}}特殊数据10000000000000000001 2#includeiostream #includecstring #define i64 long long #define INF 999999 using namespace std; i64 n,m,q; string s; i64 ans0,len0; i64 num[45][45],dp[45][100005]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinsn; lens.length(); for (int i1;ilen;i) { num[i][i]s[i-1]-0; for (int ji1;jlen;j) { if(num[i][j-1]n){ num[i][j]n1; }else{ num[i][j]num[i][j-1]*10(s[j-1]-0); if(num[i][j]n) num[i][j]n1; } } } for(i64 i0;ilen;i){ for(i64 k0;kn;k){ dp[i][k]INF; } } dp[0][0]0; for(i64 i1;ilen;i){ for(i64 k0;kn;k){ for(i64 ji-1;j0;j--){ i64 valnum[j1][i]; if(valn) continue; if(knum[j1][i]dp[j][k-val]!INF){ dp[i][k]min(dp[i][k],dp[j][k-val]1); } } } } if(dp[len][n]INF) coutdp[len][n]-1; else cout-1; return 0; }T6P2758 编辑距离 - 洛谷不用管这东西的中间状态只要管前后差异就好了。我总是跳脱不出这种思维。dp[i][j]数组表示从A的前i个转变成B的前j个需要多少步。感觉上手一下还好理解测试用例sfdqxbwgfdgw理论dp数组值012345112345221234332123443223554333665444776554自己手算模拟一遍也够了在这里就需要注意下标你得看准是i-1和j-1。在这里就把问题转换成了s1和s2相应元素的比较。#includeiostream #includecstring #define i64 long long using namespace std; i64 n,m,q; string s1,s2; i64 len1,len2; i64 dp[2005][2005]; void fun(); int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cins1s2; len1s1.length(); len2s2.length(); fun(); coutdp[len1][len2]; return 0; } void fun(){ for(i64 i1;ilen1;i) dp[i][0]i; for(i64 j1;jlen2;j) dp[0][j]j; for(i64 i1;ilen1;i){ for(i64 j1;jlen2;j){ //字符串从0开始但是标号一般从1开始所以最好要有个偏移量转换 if(s1[i-1]s2[j-1]){ dp[i][j]dp[i-1][j-1]; continue; } dp[i][j]min( min(dp[i-1][j],dp[i][j-1]), dp[i-1][j-1])1; } } for(i64 i0;ilen1;i){ for(i64 j0;jlen2;j){ coutdp[i][j]; } coutendl; } return ; }T7P1439 两个排列的最长公共子序列 - 洛谷通过上一题我已经可以切出这题的50分版本了。#includeiostream #includecstring #define i64 long long using namespace std; i64 n,m,q; i64 a[100005],b[100005]; i64 dp[1005][1005]; //dp[i][j]表示前i个和前j个的最长公共子序列长度 void fun(); int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinn; for(i64 i1;in;i){ cina[i]; } for(i64 i1;in;i){ cinb[i]; } fun(); coutdp[n][n]; return 0; } void fun(){ for(i64 i1;in;i){ for(i64 j1;jn;j){ if(a[i]b[j]){ dp[i][j]dp[i-1][j-1]1; continue; } dp[i][j]max( max(dp[i][j-1],dp[i-1][j]), dp[i-1][j-1]); } } return ; }然后看题解。题解大神发力了这居然是一个排列所以求最长上升子序列就可以了。看来是上面这题的惯性思维走不出来。对于我有一个细节理解了很久为什么是lower不能用upper。经过测试发现lower的结果是11123 upper的测试结果是12345所以你自己理解理解吧。#includeiostream #includecstring #includealgorithm #define i64 long long using namespace std; i64 n,m,q; i64 a[100005],c[100005],top0; //dp[i][j]表示前i个和前j个的最长公共子序列长度 int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinn; for(i64 i1;in;i){ cinm; a[m]i; } for(i64 i1;in;i){ cinm; i64 pa[m]; // 映射成P1中的位置 i64 idxlower_bound(c1,ctop1,p)-c; if(idxtop){ c[top]p; }else{ c[idx]p; } } couttopendl; return 0; } /* 5 4 3 1 2 5 4 3 1 2 5 */大道至简重剑无锋。T8P2679 [NOIP 2015 提高组] 子串 - 洛谷逆天思路。而且还有一个非常人才的设计滚动的意思就是i对2取余。因为只用管前后问题不会出现跨阶级的情况。还有一个细节真的细。#includeiostream #includecstring #includealgorithm #define i64 long long #define mod 1000000007 using namespace std; i64 n,m,k; char a[1005],b[1005]; i64 dp[3][205][205][3]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinnmk; for(i64 i1;in;i) cina[i]; for(i64 i1;im;i) cinb[i]; dp[0][0][0][0]1; dp[1][0][0][0]1; for(i64 i1;in;i){ for(i64 j1;jm;j){ for(i64 p1;pk;p){ if(a[i]b[j]){ dp[i%2][j][p][1](dp[(i-1)%2][j-1][p][1](dp[(i-1)%2][j-1][p-1][0]dp[(i-1)%2][j-1][p-1][1])%mod)%mod; //将当前字符纳入前一个子串并使用前一个字符的种数 //将当前字符纳入新子串但不使用前一个字符的种数 //将当前字符纳入新子串但不使用前一个字符的种数 dp[i%2][j][p][0](dp[(i-1)%2][j][p][0]dp[(i-1)%2][j][p][1])%mod; }else{ dp[i%2][j][p][1]0; dp[i%2][j][p][0](dp[(i-1)%2][j][p][0]dp[(i-1)%2][j][p][1])%mod; } } } } cout(dp[n%2][m][k][1]dp[n%2][m][k][0])%mod; return 0; }