3758 - 花店橱窗
时间限制 : 1 秒
内存限制 : 128 MB
xq和他的老婆xz最近开了一家花店，他们准备把店里最好看的花都摆在橱窗里。但是他们有很多花瓶，每个花瓶都具有各自的特点，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果。为了使橱窗里的花摆放的最合适，他们得想个办法安排每种花的摆放位置。
可是因为xq和xz每天都太忙，没有时间设计橱窗里花的摆法，所以他们想让你帮他们求出花摆放的最大美观程度和每种花所放的位置。
注：标号小花必须放在标号大的前面。
每种花放在不同的瓶子里会产生不同的美观程度，美观程度可能是正数也可能是负数。
上述例子中，花瓶与花束的不同搭配所具有的美观程度，如下表所示：
花 瓶
1 2 3 4 5
1 (杜鹃花) 7 23 -5 -24 16
2 (秋海棠) 5 21 -4 10 23
3 (康乃馨) -21 5 -4 -20 20
根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得十分难看。
题目输入
第1行：两个整数F和V，表示xq和xz一共有F种花，V个花瓶。(1<=F<=V<=100)
第2行到第F+1行：每行有V个数，表示花摆放在不同花瓶里的美观程度值value。(美观程度和不超过maxint，美观程度有正有负。)
题目输出
输出有两行：第一行为输出最大美观程度和的值，第二行有F个数表示每朵花应该摆放的花瓶的编号。
输入/输出样例
输入格式
3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20
输出格式
53 2 4 5
C++解答
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; const int N = 105; const int INF = 1<<30; int a[N][N]; int dp[N][N]; bool path[N][N]; void Print(int i,int j) { if(i == 0) return; if(path[i][j]) { Print(i-1,j-1); printf("%d ",j); } else Print(i,j-1); } int main() { int F,V; while(~scanf("%d%d",&F,&V)) { memset(path,0,sizeof(path)); for(int i=1;i<=F;i++) for(int j=1;j<=V;j++) scanf("%d",&a[i][j]); for(int i=1;i<=F;i++) for(int j=0;j<=V;j++) dp[i][j] = -INF; for(int i=1;i<=F;i++) { for(int j=i;j<=V && i <= i + F;j++) { if(dp[i-1][j-1] + a[i][j] <= dp[i][j-1]) dp[i][j] = dp[i][j-1]; else { dp[i][j] = dp[i-1][j-1] + a[i][j]; path[i][j] = 1; } } } printf("%d\n",dp[F][V]); Print(F,V); puts(""); } return 0; }