题解 | #花店橱窗#

花店橱窗

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

问题描述：略。

转移方程：

F(i,j) = max_{i < k < j}(F(i,j), F(i-1,k) + A[i][j])

状态表示：

F(i,j)表示第i个花放在第j个花瓶上时的最大值。

边界：

F(i,j) = -inf \quad if \quad 1 \leq i,j \leq N

目标：

max_{1 \leq k \leq m}(F(n,k))

总结和反思：

在刚开始用了很久想出了正确的子问题和状态表示，但是在敲代码的时候，淡化了子问题和状态表示，导致后面多了一个遍历z【此时子问题是：在前i个花放到前j个花瓶上时的最大值（好像这样z和j状态有重复】。

反思是做dp一定不要忘记dp的子问题是什么，在子问题上一定要下功夫。

代码：

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;

// #define Multiple_groups_of_examples
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<endl;
#define rep(i,x,n) for(int i = x; i <= n; i++)

#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs second

typedef long long LL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const int N = 2e2 + 21;
int num[N][N];
int f[N][N];
PII pos[N][N];
void inpfile();
void solve() {
    int n,m; cin>>n>>m;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) cin>>num[i][j], f[i][j] = -INF;
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m - (n-i); ++j) {
            for(int k = i-1; k <= j-1; ++k) {
                    // f[i][j] = max(f[i][j], f[i-1][k] + num[i][z]);
                    if(f[i][j] < f[i-1][k] + num[i][j]) {
                        pos[i][j] = {i-1,k};
                        f[i][j] = f[i-1][k] + num[i][j];
                    }
                // } 
            }
        }
    }
    // cout<<f[n][m];
    stack<int> sk;
    int ma = -INF;
    for(int i = 1; i <= m; ++i) {
        ma = max(ma, f[n][i]);
    }
    cout<<ma<<endl;
    for(int i = n; i <= m; ++i) {
        if(ma == f[n][i]) {
            sk.push(i);
            int ii = n, jj = i;
            while(pos[ii][jj].vf != 0) {
                sk.push(pos[ii][jj].vs);
                PII t = pos[ii][jj];
                ii = t.vf, jj = t.vs;
            }
            break; // 数据有点弱，没加break，也过了。
        }
    }
    while(sk.size()) {
        cout<<sk.top()<<" "; sk.pop();
    }
}
int main()
{
    #ifdef Multiple_groups_of_examples
    int T; cin>>T;
    while(T--)
    #endif
    solve();
    return 0;
}
void inpfile() {
    #define mytest
    #ifdef mytest
    freopen("ANSWER.txt", "w",stdout);
    #endif
}