sgu 104 Little shop of flowers 解题报告及测试数据

104. Little shop of flowers

time limit per test: 0.25 sec.

memory limit per test: 4096 KB

问题：

你想要将你的花窗安排得最具美感。有F束花，每一束花都不一样，至少有F个按顺序排成一行的花瓶。花瓶从左到右，依次编号1-V。而花放置的位置是可以改变的，花依次编号1到F。花的序号有一个特征，即是序号决定了花束出现在花瓶里的顺序。例如，有两束花编号i和j，满足i<j，那么i所在的花瓶一定要在j所在花瓶的左边，即是i所在花瓶序号小于j的。每一束花都只能且必须插在一个花瓶中，一个花瓶只能插一朵花，如果花瓶的个数大于花束的个数，那么将会出现空的花瓶。

每个花瓶都有一个严格的特征值。某一束花放置在某一个花瓶中有一个确定的美学价值，用整数表示。空花瓶的美学价值为1。如下表所示。

		V A S E S
		1	2	3	4	5
Bunches	1 (azaleas)	7	23	-5	-24	16
	2 (begonias)	5	21	-4	10	23
	3 (carnations)	-21	5	-4	-20	20

根据上表，例如，杜鹃花放在花瓶2中具有最大的美学价值，放在花瓶4中美学价值最低。为了使花店的美学价值最大，你需要计算出按照花的顺序将花放置在花瓶中后的最大美学价值。如果可以产生最大美学价值的放置方式不只一种，那么任何一种都是可以的，你只需要设计出一种可以了。

假设：

1 ≤ F ≤ 100 ，F是花的数量，依次编号1到F
F ≤ V ≤ 100 ，V 是花瓶的数量。
-50 £ A_ij £ 50 ，Aij是将花束i放置在花瓶j的美学价值。

输入：

第一行包含两个值，F和V。
接下来的F 行，每一行包含V个整数，因此Aij的值就是输入文件中第i+1行的第j个数字。

输出

第一行包含按照你的方案计算出的美学价值。
第二行包含F个整数，第k个数代表放置第k束花的花瓶的编号。

示例输入：

3 5

7 23 -5 -24 16

5 21 -4 10 23

-21 5 -4 -20 20

示例输出

53

2 4 5

来源： <http://acm.sgu.ru/problem.php?contest=0&problem=104>

题解：

因为花瓶放置必须按照顺序，就是说放第i个花瓶的位置一定与之前i-1个花瓶的状态有关，所以就想到了动态规划。
所有的花都必须放置在花瓶中，所以考虑第i束花应从第i个花瓶开始。状态转移方程即是 dp[i][j] = max(dp[i-1][j-1]+a[i][j],dp[i][j-1]) ，前者代表第i束花放在第j个花瓶中，后者代表将第j个花瓶空置。
路径的记录。使用二维数组 tag[N][N]，将更新的位置置为1，将空置的位置置为0。那么从后往前遍历找到最后更新的值的位置就是花放置的位置。

以下是代码：

#include <cstdio>

#include <iostream>

#include <string>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

using namespace std;

#define ss(x) scanf("%d",&x)

#define ff(i,st,ed) for(int i=st;i<ed;i++)

#define fe(i,st,ed) for(int i=st;i<=ed;i++)

#define s64(x) scanf("%I64d",&x)

#define print(x) printf("%d\n",x)

#define write() freopen("1.in","r",stdin)

typedef long long LL;

const int N = 105;

const int INF = 10000000;

int a[N][N];

int dp[N][N],tag[N][N];

int F,V;

void init(){

    ss(F);ss(V);

    fe(i,1,F)fe(j,1,V)

        ss(a[i][j]);

    ff(i,0,N)ff(j,0,N){

        dp[i][j]=-INF;

        tag[i][j]=0;

    }

}

void solve(){

    fe(i,0,F)

    fe(j,i,V){   //第二层循环从i开始

        if(dp[i-1][j-1]+a[i][j]>dp[i][j-1]){

            tag[i][j]=1;

            dp[i][j]= dp[i-1][j-1]+a[i][j];

        }else dp[i][j]=dp[i][j-1];  //状态转移方程

    }

    print(dp[F][V]);

    int k = F,path[N];

    //从后往前遍历，寻找最后更新位置

    for(int i = V;i>=1;i--)

        if(tag[k][i] && k >=1)path[k--]=i;

    fe(i,1,F)printf("%d ", path[i]);//输出

}

int main(){

    //write();

    init();

    solve();

}

秒客网

sgu 104 Little shop of flowers 解题报告及测试数据

相关文章