如何免费开自己的网站,学校网站建设情况,dz wordpress互通,网站上图片可以做商业作品吗传送门 文章目录解析问题代码解析
一道很正常的动态规划 dp[i][j]表示到第j个花瓶放了第j朵花的dp最优值 注意#xff1a;是严格使第i朵放在j瓶 找到最优解递归输出即可
问题
又是初始化的问题#xff01;#xff01;#xff01; 一开始把dp赋值成负无穷时落掉了j0的一行…传送门
文章目录解析问题代码解析
一道很正常的动态规划 dp[i][j]表示到第j个花瓶放了第j朵花的dp最优值 注意是严格使第i朵放在j瓶 找到最优解递归输出即可
问题
又是初始化的问题 一开始把dp赋值成负无穷时落掉了j0的一行 但到0个花瓶放了i朵花显然也是不合法的i不等于0时 导致出错 以后动态规划一定要重视初始化
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N105;
int v[N][N];
int dp[N][N];//j瓶放到第i朵
int n,m;
int a,b,c;
int pre[N][N];
void print(int k,int pl){if(k0) return;print(k-1,pre[k][pl]);printf(%d ,pl);
}
int main(){scanf(%d%d,n,m);for(int i1;in;i){dp[i][0]-2e9;for(int j1;jm;j) scanf(%d,v[i][j]),dp[i][j]-2e9;}for(int j0;jm;j) dp[0][j]0;for(int j1;jm;j){for(int i1;in;i){for(int ki-1;kj;k){if(dp[i][j]dp[i-1][k]v[i][j]){dp[i][j]dp[i-1][k]v[i][j];pre[i][j]k;}}}}int ans-2e9,pl;for(int j1;jm;j){if(ansdp[n][j]){ansdp[n][j];plj;}}printf(%d\n,ans);print(n,pl);return 0;
}
/*
3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20
*/
