京东网站建设项目需求分析报告,怎么套模板 网站模板,互联网保险的风险,汕头手机建站模板题目传送门
思路
因为占据的连通块的左端点先递减、后递增#xff0c;右端点先递增、后递减#xff0c;所以设 f i , j , l , r , x ( 0 / 1 ) , y ( 0 / 1 ) f_{i,j,l,r,x(0/1),y(0/1)} fi,j,l,r,x(0/1),y(0/1) 为前 i i i 行中#xff0c;选择 j j j 个方格#x…题目传送门
思路
因为占据的连通块的左端点先递减、后递增右端点先递增、后递减所以设 f i , j , l , r , x ( 0 / 1 ) , y ( 0 / 1 ) f_{i,j,l,r,x(0/1),y(0/1)} fi,j,l,r,x(0/1),y(0/1) 为前 i i i 行中选择 j j j 个方格其中第 i i i 行选择的区间的左端点为 l l l右端点为 r r r x x x 表示左端点是否出现递增 y y y 表示右端点是否递增的所有方案的最大石油数量。
容易列出状态转移方程 f i , j , l , r , 0 , 0 max { f i − 1 , j − ( r − l 1 ) , a , b , 0 , 0 , f i − 1 , j − ( r − l 1 ) , a , b , 0 , 1 } s i , r − s i , l − 1 f i , j , l , r , 0 , 1 max { f i − 1 , j − ( r − l 1 ) , a , b , 0 , 1 } s i , r − s i , l − 1 f i , j , l , r , 1 , 0 max { f i − 1 , j − ( r − l 1 ) , a , b , 0 , 0 , f i − 1 , j − ( r − l 1 ) , a , b , 0 , 1 , f i − 1 , j − ( r − l 1 ) , a , b , 1 , 0 , f i − 1 , j − ( r − l 1 ) , a , b , 1 , 1 } s i , r − s i , l − 1 f i , j , l , r , 1 , 1 max { f i − 1 , j − ( r − l 1 ) , a , b , 0 , 1 , f i − 1 , j − ( r − l 1 ) , a , b , 1 , 1 } s i , r − s i , l − 1 f_{i,j,l,r,0,0}\max\{f_{i-1,j-(r-l1),a,b,0,0},f_{i-1,j-(r-l1),a,b,0,1}\}s_{i,r}-s_{i,l-1}\\ f_{i,j,l,r,0,1}\max\{f_{i-1,j-(r-l1),a,b,0,1}\}s_{i,r}-s_{i,l-1}\\ f_{i,j,l,r,1,0}\max\{f_{i-1,j-(r-l1),a,b,0,0},f_{i-1,j-(r-l1),a,b,0,1},f_{i-1,j-(r-l1),a,b,1,0},f_{i-1,j-(r-l1),a,b,1,1}\}s_{i,r}-s_{i,l-1}\\ f_{i,j,l,r,1,1}\max\{f_{i-1,j-(r-l1),a,b,0,1},f_{i-1,j-(r-l1),a,b,1,1}\}s_{i,r}-s_{i,l-1}\\ fi,j,l,r,0,0max{fi−1,j−(r−l1),a,b,0,0,fi−1,j−(r−l1),a,b,0,1}si,r−si,l−1fi,j,l,r,0,1max{fi−1,j−(r−l1),a,b,0,1}si,r−si,l−1fi,j,l,r,1,0max{fi−1,j−(r−l1),a,b,0,0,fi−1,j−(r−l1),a,b,0,1,fi−1,j−(r−l1),a,b,1,0,fi−1,j−(r−l1),a,b,1,1}si,r−si,l−1fi,j,l,r,1,1max{fi−1,j−(r−l1),a,b,0,1,fi−1,j−(r−l1),a,b,1,1}si,r−si,l−1 。
注意由于联通所以 r ≥ a r\ge a r≥a 且 l ≤ b l\le b l≤b。因为递增递减所以当 x 0 x0 x0 时 l ≤ a l\le a l≤a当 x 1 x1 x1 时 l ≥ a l\ge a l≥a当 y 0 y0 y0 时 r ≤ b r\le b r≤b当 y 1 y1 y1 时 r ≥ b r\ge b r≥b。 s i , j s_{i,j} si,j 为第 i i i 行的前缀和不是二维前缀和。
最终答案为 max { f i , k , l , r , x , y } \max\{f_{i,k,l,r,x,y}\} max{fi,k,l,r,x,y}输出路径可以存一个结构体 l a i , j , l , r , x , y la_{i,j,l,r,x,y} lai,j,l,r,x,y 统计 f i , j , l , r , x , y f_{i,j,l,r,x,y} fi,j,l,r,x,y 从哪里转移来。
思路容易想代码细节却很多本人被硬控了几个小时。
代码
//要C14(GCC 9)不然会RE
#include bits/stdc.h
using namespace std;
const int N25;
struct Last{int i,j,l,r,x,y;
}la[N][N*N][N][N][2][2];
int n,m,k,a[N][N],s[N][N],f[N][N*N][N][N][2][2];
int main(){scanf(%d%d%d,n,m,k);for(int i1;in;i)for(int j1;jm;j){scanf(%d,a[i][j]);s[i][j]s[i][j-1]a[i][j];}for(int i1;in;i)for(int j1;ji*m;j)for(int l1;lm;l)for(int rl;rm;r){if(r-l1(i-1)*mj || jr-l1)continue;int sums[i][r]-s[i][l-1];if(i1){f[i][j][l][r][0][0]f[i][j][l][r][0][1]f[i][j][l][r][1][0]f[i][j][l][r][1][1]sum;continue;}//x0,y0for(int x1;xm;x)for(int yx;ym;y)if(!(yl || xr) xl yr){//注意要联通,l要递减,r要递减if(f[i-1][j-(r-l1)][x][y][0][0]sumf[i][j][l][r][0][0])f[i][j][l][r][0][0]f[i-1][j-(r-l1)][x][y][0][0]sum,la[i][j][l][r][0][0]{i-1,j-(r-l1),x,y,0,0};if(f[i-1][j-(r-l1)][x][y][0][1]sumf[i][j][l][r][0][0])f[i][j][l][r][0][0]f[i-1][j-(r-l1)][x][y][0][1]sum,la[i][j][l][r][0][0]{i-1,j-(r-l1),x,y,0,1};}//x0,y1for(int x1;xm;x)for(int yx;ym;y)if(!(yl || xr) xl yr){//l要递减,r要递增if(f[i-1][j-(r-l1)][x][y][0][1]sumf[i][j][l][r][0][1])f[i][j][l][r][0][1]f[i-1][j-(r-l1)][x][y][0][1]sum,la[i][j][l][r][0][1]{i-1,j-(r-l1),x,y,0,1};}//x1,y0for(int x1;xm;x)for(int yx;ym;y)if(!(yl || xr) xl yr){//l要递增,r要递减if(f[i-1][j-(r-l1)][x][y][0][0]sumf[i][j][l][r][1][0])f[i][j][l][r][1][0]f[i-1][j-(r-l1)][x][y][0][0]sum,la[i][j][l][r][1][0]{i-1,j-(r-l1),x,y,0,0};if(f[i-1][j-(r-l1)][x][y][0][1]sumf[i][j][l][r][1][0])f[i][j][l][r][1][0]f[i-1][j-(r-l1)][x][y][0][1]sum,la[i][j][l][r][1][0]{i-1,j-(r-l1),x,y,0,1};if(f[i-1][j-(r-l1)][x][y][1][0]sumf[i][j][l][r][1][0])f[i][j][l][r][1][0]f[i-1][j-(r-l1)][x][y][1][0]sum,la[i][j][l][r][1][0]{i-1,j-(r-l1),x,y,1,0};if(f[i-1][j-(r-l1)][x][y][1][1]sumf[i][j][l][r][1][0])f[i][j][l][r][1][0]f[i-1][j-(r-l1)][x][y][1][1]sum,la[i][j][l][r][1][0]{i-1,j-(r-l1),x,y,1,1};}//x1,y1for(int x1;xm;x)for(int yx;ym;y)if(!(yl || xr) xl yr){//l要递增,r要递增if(f[i-1][j-(r-l1)][x][y][0][1]sumf[i][j][l][r][1][1])f[i][j][l][r][1][1]f[i-1][j-(r-l1)][x][y][0][1]sum,la[i][j][l][r][1][1]{i-1,j-(r-l1),x,y,0,1};if(f[i-1][j-(r-l1)][x][y][1][1]sumf[i][j][l][r][1][1])f[i][j][l][r][1][1]f[i-1][j-(r-l1)][x][y][1][1]sum,la[i][j][l][r][1][1]{i-1,j-(r-l1),x,y,1,1};}}int ans0;Last tmp;for(int i1;in;i)for(int l1;lm;l)for(int rl;rm;r){if(f[i][k][l][r][0][0]ans)ansf[i][k][l][r][0][0],tmp{i,k,l,r,0,0};//tmp存储当前的状态if(f[i][k][l][r][0][1]ans)ansf[i][k][l][r][0][1],tmp{i,k,l,r,0,1};if(f[i][k][l][r][1][0]ans)ansf[i][k][l][r][1][0],tmp{i,k,l,r,1,0};if(f[i][k][l][r][1][1]ans)ansf[i][k][l][r][1][1],tmp{i,k,l,r,1,1};}printf(Oil : %d,ans);while(tmp.j tmp.i){//输出路径for(int itmp.l;itmp.r;i)printf(\n%d %d,tmp.i,i);tmpla[tmp.i][tmp.j][tmp.l][tmp.r][tmp.x][tmp.y];}return 0;
}
