题意
插花，给你若干花瓶和若干把花，花瓶个数大于等于花的把数，每把花都不一样，要求你让每把花都插进花瓶里面，花瓶不一定每个都要用，但是你必须保证插完之后花的排列顺序和原来给出的一样。然后给了你一个花插进花瓶之后产生的美学价值对照表，要你设计一种方案使得这样插花所达到的美学价值最大。
思路
典型的背包问题，我们设计一个二维dp数组dp[i][j]，令i表示当前已经考虑到第几把花，令j表示对于当前这把花我们插入到前j个花瓶，那么我们一把一把花处理，对于每把花枚举其插入每个花瓶的结果，同时要继承上一把花插入到这个花瓶之前的全部状态中最优的那个（因为要保证有序）。最后枚举dp[n][j]的j，找到最佳状态就好了。
接下来要考虑怎么输出最优方案，其实不难想，我们可以给dp数组加上一维或者单开一个pre[i][j]数组，与dp数组平行工作，保存当前状态的前置状态，最后顺着最佳状态不断回溯输出就搞定了。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; int aes[105][105]; int dp[105][105][2]; // 0 is value 1 is pre int main(){ int f = 0,v = 0; scanf(" %d %d",&f,&v); memset(aes, 0, sizeof(aes)); for (int i = 1; i <= f; i++) { for (int j = 1; j <= v; j++) { scanf(" %d",&aes[i][j]); } } memset(dp, 0xf3f3, sizeof(dp)); for (int i = 1; i <= v; i++) { dp[1][i][0] = aes[1][i]; dp[1][i][1] = 0; } for (int i = 1; i <= f; i++) { for (int j = 2; j <= v; j++) { for (int k = 1;k < j; k++) { if (dp[i][j][0] < dp[i-1][k][0] + aes[i][j]) { dp[i][j][0] = dp[i-1][k][0] + aes[i][j]; dp[i][j][1] = k; } } } } int maxn = 0xf3f3f3f3,maxi = 0; for (int i = 1; i <= v; i++) { if (dp[f][i][0] > maxn) { maxn = dp[f][i][0]; maxi = i; } } stack<int> curstk; int cur = maxi; while (f) { curstk.push(cur); cur = dp[f--][cur][1]; } printf("%dn",maxn); while (curstk.size() > 1) { printf("%d ",curstk.top()); curstk.pop(); } printf("%dn",curstk.top()); curstk.pop(); return 0; } |
