怀化市住房和城乡建设局网站,网站维护公告模板,施工企业税款缴纳,网站备案修改原题链接#xff1a; https://codeforces.com/gym/104354
题意#xff1a;
有一个n*m的矩阵#xff0c;只有三种字符#xff1a;0,1和?。从[1,1]走到[n,m],每次只能向下走或者向下走。当走到1的时候得一分#xff0c;走到0的时候不得分#xff0c;走到?的时候可以将他…原题链接 https://codeforces.com/gym/104354
题意
有一个n*m的矩阵只有三种字符0,1和?。从[1,1]走到[n,m],每次只能向下走或者向下走。当走到1的时候得一分走到0的时候不得分走到?的时候可以将他变为1从而得到一分或者不变求所有从[1,1]走到[n,m]的路径的得分的最大值
思路
f[i][j][k]表示走到[i,j]恰好有k个?变成1的方案数的最大得分 状态转移 a[i][j]‘0’:f[i][j][k]max(f[i-1][j][k],f[i][j-1][k]) a[i][j]‘1’:f[i][j][k]max(f[i-1][j][k]1,f[i][j-1][k]1) a[i][j]‘?’: 改:f[i][j][k]max(f[i-1][j][k-1]1,f[i][j-1][k-1]1) 不改f[i][j][k]max(f[i-1][j][k],f[i][j-1][k])
那么这样的空间复杂度是n* m * x会mle
于是考虑将数组优化到二维f[j][k]
1.将k从大到小枚举 在转移的时候如果按正常枚举就会出现重复的情况这时候只需要将k从大到小进行枚举就避免了重复
#includebits/stdc.h
using namespace std;
int n,m,x;
int f[505][1005];
char a[505][505];
bool cheek(int x,int y){if(x1xny1ym) return true;else return false;
}
void sove(){scanf(%d%d%d,n,m,x);for(int i1;in;i){for(int j1;jm;j){cina[i][j];}}for(int j0;jm;j){for(int k0;kx;k){f[j][k]-0x3f3f3f3f;}}if(a[1][1]1){f[1][0]1;}else if(a[1][1]0){f[1][0]0;}else{f[1][1]1;f[1][0]0;}for(int i1;in;i){for(int j1;jm;j){for(int kx;k0;k--){if(a[i][j]1){if(cheek(i-1,j)){f[j][k]max(f[j][k],f[j][k]1);}if(cheek(i,j-1)){f[j][k]max(f[j][k],f[j-1][k]1);}}else if(a[i][j]0){if(cheek(i,j-1)){f[j][k]max(f[j][k],f[j-1][k]);} }else{if(cheek(i-1,j)){if(k-10) f[j][k]max(f[j][k],f[j][k-1]1);}if(cheek(i,j-1)){f[j][k]max(f[j-1][k],f[j][k]);if(k-10)f[j][k]max(f[j][k],f[j-1][k-1]1);} }}}}int ans0;for(int i0;ix;i){ansmax(ans,f[m][i]);}coutansendl;
}
int main(){int t;scanf(%d,t);while(t--){sove();}return 0;
}2.滚动数组 在转移的时候只用到了i和i-1层那么我们就将i这一维开两个在转移的时候在两维之间相互转移就可以了
#includebits/stdc.h
using namespace std;
int n,m,x;
int f[3][505][1005];
char a[505][505];
bool cheek(int x,int y){if(x1xny1ym) return true;else return false;
}
void sove(){scanf(%d%d%d,n,m,x);for(int i1;in;i){for(int j1;jm;j){cina[i][j];}}for(int i0;i3;i){for(int j0;jm;j){for(int k0;kx;k){f[i][j][k]-0x3f3f3f3f;}}
}if(a[1][1]1){f[1][1][0]1;}else if(a[1][1]0){f[1][1][0]0;}else{f[1][1][1]1;f[1][1][0]0;}for(int i1;in;i){for(int j1;jm;j){for(int k0;kx;k){if(a[i][j]1){if(cheek(i-1,j)){f[i1][j][k]max(f[i1][j][k],f[i-11][j][k]1);}if(cheek(i,j-1)){f[i1][j][k]max(f[i1][j][k],f[i1][j-1][k]1);}}else if(a[i][j]0){if(cheek(i-1,j)){f[i1][j][k]max(f[i1][j][k],f[i-11][j][k]);}if(cheek(i,j-1)){f[i1][j][k]max(f[i1][j][k],f[i1][j-1][k]);} }else{if(cheek(i-1,j)){f[i1][j][k]max(f[i1][j][k],f[i-11][j][k]);if(k-10)f[i1][j][k]max(f[i1][j][k],f[i-11][j][k-1]1);}if(cheek(i,j-1)){f[i1][j][k]max(f[i1][j][k],f[i1][j-1][k]);if(k-10)f[i1][j][k]max(f[i1][j][k],f[i1][j-1][k-1]1);} }}}}int ans0;for(int i0;ix;i){ansmax(ans,f[n1][m][i]);} coutansendl;
}
int main(){int t;scanf(%d,t);while(t--){sove();}return 0;
}
