P10997 【MX-J3-T4】 Partition太长了。看原题吧好像是一个trick 非常巧妙感觉要是紫。发现红黄绿橙的分界线呈两条对角线的样子。其中黄绿最高点不增橙绿最高点不降。再看这个分数怎么统计先都认为为1 11,然后橙绿加一黄绿加二。发现这样相应的分数是正确的红1橙:112,黄123绿1124.又因为黄绿线和橙绿线是互相独立的分开DP即可。其中我们设用( i , j ) (i,j)(i,j)代表这个格子左上角的分界点。f 1 i , j f1_{i,j}f1i,j​表示到第i ii列分界点在j jj及以下最高的黄绿得分。f 2 i , j f2_{i,j}f2i,j​表示到第i ii列分界点在j jj及以上最高的橙绿得分。f 1 i , j max ⁡ ( f 1 i − 1 , j , f 1 i , j − 1 u d i , j − 1 ) f1_{i,j} \max(f1_{i-1,j},f1_{i,j-1}ud_{i,j-1})f1i,j​max(f1i−1,j​,f1i,j−1​udi,j−1​)从上一列分界或是更低的格子分界得到的最优值。f 2 f2f2同理。启示把 数 拆分分别统计。code#includebits/stdc.husingnamespacestd;#definelllonglongconstll INF0x3f3f3f3f3f3f3f3f;constintN2005;intn,m;ll f1[N][N],f2[N][N];ll ud[N][N];ll a[N][N];ll sum;intmain(){scanf(%d%d,n,m);for(inti1;in;i){for(intj1;jm;j){scanf(%lld,a[i][j]);suma[i][j];}}for(inti0;in1;i){for(intj0;jm1;j){f1[i][j]f2[i][j]-INF;}}for(intin;i1;i--){for(intj1;jm;j){ud[i][j]ud[i1][j]a[i][j];}}f1[0][1]f2[0][m1]0;for(inti1;in1;i){for(intj1;jm1;j){//黄绿f1[i][j]max(f1[i-1][j],f1[i][j-1]ud[i][j-1]);}for(intjm1;j1;j--){f2[i][j]max(f2[i-1][j],f2[i][j1]ud[i][j]);//因为记的是左上角。}}printf(%lld\n,sumf1[n1][m1]*2f2[n1][1]);return0;}