社区讨论

蒟蒻 can't understand ! 82pts

LLQ_Q
P1854[IOI 1999] 花店橱窗布置参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@m4cvvrh2
此快照首次捕获于
2024/12/06 23:11
去年
此快照最后确认于
2024/12/07 10:11
去年
查看原帖

思路：

对于 dp[i][j] 表示为插入前 i 只花，最多使用 (1~j) 个花瓶所产生的最大价值。

转移方程：

1、dp[i][j]=dp[i−1][j−1]+v[i][j]1、dp[i][j]=dp[i-1][j-1]+v[i][j]
2、dp[i][j]=max(dp[i][j],dp[i][j−1])2、dp[i][j]=max(dp[i][j],dp[i][j-1])

解释：

对于 dp[i][j]=dp[i−1][j−1]+v[i][j]dp[i][j]=dp[i-1][j-1]+v[i][j]

对于即将插入 花瓶j 的 花i ，前 1~(i-1) 只花 最多使用 (j-1) 个花瓶,根据定义 花(1~i) 产生的最大价值为 dp[i-1][j-1] （为防止因花的价值为负数而导致不选的情况，将 dp[i-1][j-1]+v[i][j] 设置为 dp[i][j] 的初始值

对于 dp[i][j]=max(dp[i][j],dp[i][j−1])dp[i][j]=max(dp[i][j],dp[i][j-1])

对于已经插入 花瓶j 的 花i ：
1、将 花i 放入 花瓶j ，在 (1~j)个花瓶 中最优，则 dp[i][j] 仍为初始值
2、将 花i 放入 花瓶j ，在 (1~j-1)个花瓶 中存在更优解，则继承 dp[i][j-1] 的值（从最优解一路继承过来的，故为 j-1 ）
怎么感觉像是在写题解
CPP
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e2+2,INF=0-0x3f3f3f3f;
int n,m,v[MAXN][MAXN],dp[MAXN][MAXN],ans_way[MAXN],ans_l=0;
int main(){
	scanf("%d%d",&n,&m);
	memset(dp,INF,sizeof(dp));
	for(int i=0;i<=m;i++) dp[0][i]=0;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++) scanf("%d",&v[i][j]);
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++){
	    	dp[i][j]=dp[i-1][j-1]+v[i][j];
			dp[i][j]=max(dp[i][j],dp[i][j-1]); 
		}
	printf("%d\n",dp[n][m]);
	int l=m;
	for(int i=n;i>=1;i--){
		while(dp[i][l]==dp[i][l-1]) l--;
		if(dp[i][l]!=dp[i-1][l]){
			ans_way[++ans_l]=l;
			l--;
		}
    } 
    for(int i=ans_l;i>=1;i--) printf("%d ",ans_way[i]);
	return 0; 
}

回复

共 1 条回复，欢迎继续交流。

正在加载回复...