题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) 动态规划 $O(n^2)$

这里放到这里那么肯定就是动态规划的题目了

对于这种题目 我们要找到的东西有以下几种

1. 所需要表示的状态是什么
2. 每个状态的阶段是什么
3. 状态之间是如何转移的
4. 状态的其实状态和最终状态

对于这个题目 从阶段入手 肯定就是我已经摆好了i朵花作为一个阶段
那么考虑接下来的阶段 对于第i+1花 单纯的dp[i] 肯定表示不了所有状态 还需要一个维度
那么就可以想到用dp[i][j] 表示当前第i朵花 摆放的位置在第j个位置的时候的最大值

那么就有状态转移方程 dp[i][j] = max(dp[i][j],dp[i-1][k] + a[i][j])

其中k是小于我的花当前摆放的位置的 起始状态 dp[0][0] = -10000
目标状态 max(dp[n][k]) n <= k <= m;
// 注意把所有的dp初始化为-inf

时间复杂度分析：blablabla

C++ 代码

#include <bits/stdc++.h> // 舒服啊  就是从各种子问题转移后来 找到每个决策的阶段！！！

using namespace std;

const int maxn = 1e2 + 10;

int val[maxn][maxn],dp[maxn][maxn];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d",&val[i][j]);
            dp[i][j] = -1000;
        }
    }

    // start dp[all][all] = -inf,end dp[n][can in];
    for(int i = 1; i <= n; i++) // 前i个
    {
        for(int j = i; j <= m - (n - i); j++) // 放在j的位置上
        {
            for(int k = i - 1; k < j; k++) // 不能和我放在一起
            {
                dp[i][j] = max(dp[i][j],dp[i-1][k] + val[i][j]);
            }
        }
    }
    int ans = -1000;
    for(int i = 1; i <= m; i++)
    {
        ans = max(ans,dp[n][i]);
    }
    printf("%d\n",ans);
    int mid = ans;
    stack<int> pos;
    for(int i = n; i >= 1; i--)
    {
        int t = m;
        for(int j = m; j >= 1; j--)
        {
            if(dp[i][j] == ans)
            {
                t = j;
            }
        }
        pos.push(t);ans -= val[i][t];
    }
    while(!pos.empty())
    {
        printf("%d ",pos.top());pos.pop();
    }
    return 0;
}