青岛安装建设股份有限公司网站,石家庄网站模板建站,网页设计报告模板免费,环球网题目描述 解析
头疼 什么破题 就是一个dp寻找最优性决策的常规题 但是要输出过程#xff0c;可以使用递归输出 但是#xff01; 这题数据的意思是#xff1a;存在a[i]a[i1]的情况#xff0c;且在不影响利润的情况下#xff0c;机器要尽可能的用完 这河里吗 可能是机器多了…题目描述 解析
头疼 什么破题 就是一个dp寻找最优性决策的常规题 但是要输出过程可以使用递归输出 但是 这题数据的意思是存在a[i]a[i1]的情况且在不影响利润的情况下机器要尽可能的用完 这河里吗 可能是机器多了烧手吧。。。 我考虑了这样的情况甚至连数列出现下降也考虑了但是与题目意图恰好相反。。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
int n,m;
const int N150;
ll a[N][N];
struct node{ll x,now,last;
}dp[N][N];
void print(int id,int left,int num){if(id0) return;for(int inum;i0;i--){if(dp[id-1][num-i].xa[id][i]left){print(id-1,left-a[id][i],num-i);printf(%d %d\n,id,i);return;}}
}
int main(){scanf(%d%d,n,m);for(int i1;in;i){for(int j1;jm;j) scanf(%lld,a[i][j]);}for(int i1;in;i){for(int j1;jm;j){for(int kj;k0;k--){if(dp[i][j].xdp[i-1][j-k].xa[i][k]){dp[i][j].xmax(dp[i][j].x,dp[i-1][j-k].xa[i][k]);}}
// printf(i%d j%d dp%d\n,i,j,dp[i][j].x);}}printf(%lld\n,dp[n][m].x);int ansdp[n][m].x;print(n,ans,m);return 0;
}
/*for(int in;i1;i--){ans[i]pl-dp[i][pl].last;pldp[i][pl].last;}for(int i1;in;i){printf(%d %lld\n,i,ans[i]);}
2 5
8 2 2 2 2
2 5 2 2 2
*/
