题解 | #花店橱窗#

花店橱窗

https://ac.nowcoder.com/acm/problem/51216

解法一:暴力dfs,本解法复杂度过大,只能通过0%的测试点

#include <iostream>

using namespace std;

long long bu[110][110];
int a[110], st[110], ret[110];

int f, v;
long long ans = 0LL;

void dfs(int x)
{
    if(x >= f)
    {
        long long sum = 0LL;
        for(int i = 1; i <= f; i++) sum += bu[i][a[i]];
        
        if(sum > ans) 
        {
            ans = sum;
            for(int i = 1; i <= f; i++) ret[i] = a[i];
        }
    }
    
    for(int i = 1; i <= v; i++)
    {
        if(st[i]) continue;
        
        a[x] = i, st[i] = 1;
        dfs(x + 1);
        a[x] = 0, st[i] = 0;
    }
}

int main()
{
    cin >> f >> v;
    
    for(int i = 1; i <= f; i++)
        for(int j = 1; j <= v; j++)
            cin >> bu[i][j];
    
    dfs(1);
    
    cout << ans << endl;
    for(int i = 1; i <= f; i++) cout << ret[i] << ' ';
    
    return 0;
}

解法二:动态规划,相对于dfs进行了许多层递归大大减少了占用的空间.

#include <iostream>
#include <vector>

using namespace std;

int dp[110][110], v[110][110];
vector <int> ret;

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)        //dp[i][j]表示将第i朵花插入第j个花瓶里
            cin >> v[i][j], dp[i][j] = -0x3f3f3f3f;

    for (int i = 1; i <= n; i++)
        for (int j = i; j <= m - (n - i); j++)        //j表示可放入的合法区间
            for (int k = i - 1; k < j; k++)           //k用于找出当前可以得到的最大值
                dp[i][j] = max(dp[i][j], dp[i - 1][k] + v[i][j]);

    int ans = -0x3f3f3f3f;
    for (int i = 1; i <= m; i++) ans = max(ans, dp[n][i]);
    cout << ans << endl;

    for (int i = n; i > 0; i --)        //反向得出花瓶编号
        for (int j = 1; j <= m; j ++)   //令j从1开始,得出字典序最大的序列
            if (dp[i][j] == ans) {
                ret.push_back(j);
                ans -= v[i][j];
                break;
            }

    for (int i = ret.size() - 1; i >= 0; i --) cout << ret[i] << ' ';

    return 0;
}