题目背景
曾经幻想过未来的风景
或许有着另外一片天
小镇的远方
有着深远的回忆
也有着富有深情的诗篇
题目描述
Chino非常注重自己的成绩
Chino有 m 种方式给自己增加 rp 以增加成绩，她的每种增加 rp 的方式都有 n 个阶段，第 iii 种的第 j 个阶段增加的 rp 表示为 Aij ，表示连续进行了 j 天第 i 种增加 rp 的方式
Chino连续进行同一种方式，效果可能更好也可能更差，她想要知道在 n 天里能获得的最大 rp ，你能帮帮可爱的Chino吗？
输入输出格式
输入格式：
第一行，两个正整数 n ， m
接下来 m 行，第 i+1 行为 n 个整数( Ai1 - Ain )
输出格式：
一行一个数，最大的 rp
思路：
这道题一眼DP
但是n和m都不小
标准的nm^2过不了
于是我们就开始优化
我们可以开一个dp[i][j][k]数组
表示当前在i位，当前数字为j，j的长度为k
转移可以简化为两种：前面不是j的，前面是j的
分别转移即可
这样复杂度降到了n*n*m
还差不多，能过
但空间也是...所以我们要滚动数组
OK
代码：
// luogu-judger-enable-o2 #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include<iostream> #include<cstdio> #define rii register int i #define rij register int j #define rik register int k //#define int long long using namespace std; int x[10001][101],n,m; long long dpa[10001][101]; long long dpb[10001][101]; long long zd,cd,wz,lzd,lcd,lwz; inline int rd() { char ch = getchar(); int x = 0, f = 1; while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while('0' <= ch && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } signed main() { // scanf("%d%d",&n,&m); n=rd(); m=rd(); for(rii=1;i<=m;i++) { for(rij=1;j<=n;j++) { x[i][j]=rd(); // scanf("%d",&x[i][j]); // qzh[i][j]+=qzh[i-1][j]; } } for(rii=1;i<=n;i++) { cd=lcd,zd=lzd,wz=lwz; for(rij=1;j<=m;j++) { for(rik=1;k<=i-1;k++) { dpa[j][k+1]=dpb[j][k]+x[j][k+1]; if(dpa[j][k+1]>=lzd) { if(lwz!=j) { lcd=lzd; } lzd=dpa[j][k+1]; lwz=j; } } if(wz==j) { dpa[j][1]=cd+x[j][1]; } else { dpa[j][1]=zd+x[j][1]; } if(dpa[j][1]>=lzd) { if(lwz!=j) { lcd=lzd; } lzd=dpa[j][1]; lwz=j; } } if(i==n) { cout<<lzd; return 0; } for(rij=1;j<=m;j++) { for(rik=1;k<=i;k++) { dpb[j][k]=dpa[j][k]; } } } }