poj 1157(SGU 104) 动态规划（花瓶插花）

poj 1157(SGU 104) 动态规划（花瓶插花）

题意：有F种花（编号为1-F），将其插入V（V>F）个花瓶里。插花要按照顺序，即编号较小的花只能插在编号较大的花的左边。不同花插入不同的花瓶有不同的美观程度，求最大的美观程度。

思路：动态规划。dp[i][j]表示前i种花插入前j个花瓶的最大美观程度。对第i朵花分类：1、若第i朵花插在第j个花瓶中，则dp[i][j] = dp[i-1][j-1]+s[i][j]；2、若第j个花瓶空着，则dp[i][j] = dp[i][j-1];

综上，状态方程为：dp[i][j] = max(dp[i-1][j-1]+s[i][j],dp[i][j-1]);

注意：由于美观程度的范围为[-50,50],所以需要处理，即将美观程度加上50，最后减去n*50

SGU 104与poj这道题目描述完全相同，但是需要另外输出方案（任意一种方案即可）。用一个数组记录动归的路径，递归输出即可。

#include <stdio.h>
#include <string.h>
#define N 102
#define MIN -0x3fffffff
#define max(a,b) a>b?a:b
int n,m;
int dp[N][N],s[N][N];int main(){freopen(&#","r",stdin);while(scanf("%d %d",&n,&m)!=EOF){int i,j;memset(dp,0,sizeof(dp));for(i = 1;i<=n;i++)for(j = 1;j<=m;j++){scanf("%d",&s[i][j]);}for(i = 1;i<=n;i++)for(j = 1;j<=m;j++)dp[i][j] = max(dp[i-1][j-1]+s[i][j]+50,dp[i][j-1]);printf("%dn",dp[n][m]-n*50);}return 0;
}

SGU104追加输出方案的代码：

#include <stdio.h>
#include <string.h>
#define N 105
int v[N][N],dp[N][N],path[N][N];
int n,m;
void print(int x,int y){int i;if(!x)return ;for(i = y;i>=1;i--){if(path[x][i] == 2){//表示第x朵花就插在第i个花盆中否则表示第i个花盆空着print(x-1,i-1);if(x != n)printf("%d ",i);elseprintf("%dn",i);			return ;}}
}
int main(){int i,j;freopen(&#","r",stdin);memset(dp,0,sizeof(dp));scanf("%d %d",&n,&m);for(i = 1;i<=n;i++)for(j = 1;j<=m;j++){scanf("%d",&v[i][j]);v[i][j] += 50;}for(i = 1;i<=n;i++){for(j = 1;j<=m;j++)if(dp[i-1][j-1]+v[i][j] >= dp[i][j-1]){dp[i][j] = dp[i-1][j-1] + v[i][j];path[i][j] = 2;}else{dp[i][j] = dp[i][j-1];path[i][j] = 1;}}printf("%dn",dp[n][m]-n*50);print(n,m);return 0;
}