SGU 104 Little shop of flowers【DP】

浪(吃)了一天，水道题冷静冷静....

题目链接：

http://acm.sgu.ru/problem.php?contest=0&problem=104

题意：

给定每朵花放在每个花盆的值，编号大的花只能放在编号小的花的后面，每朵花都要放到花盆里，问如何放才能使得总值最大？

分析：

还是一道比较水的dp...

每个位置有两种情况：放与不放。

不放的话\(dp[i][j-1][0]\)就等于前面最近的放了花盆的值。

放的话，就更新\(dp[i][j][1]\)。

这样保证对于每个花盆\(i\)花\(j\)，\(max(dp[i - 1][j - 1][0] ,dp[i - 1][j - 1][1])\)表示放置第\(j-1\)号花后得到的最大的值。

最后逆推一遍，获得路径即可。

代码：

#include<cstdio>

#include<iostream>

#include<stack>

#include<cstring>

using namespace std;

const int maxn = 100 + 5;

int dp[maxn][maxn][2];

int v[maxn][maxn];

stack<int>s;

int main (void)

{

    int n, m;

    scanf("%d%d", &m, &n);

    for(int i = 1; i <= m; i++){

        for(int j = 1; j <= n; j++){

            scanf("%d", &v[i][j]);

        }

    }

    memset(dp, -0x3f, sizeof(dp));

    dp[0][0][0] = 0;

    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= m; j++){

            dp[i][j - 1][0] = max(dp[i - 1][j - 1][0] ,dp[i - 1][j - 1][1]);

            dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + v[j][i];

        }

    }

    int ans = max(dp[n][m][1], dp[n][m][0]);

    printf("%d\n", ans);

    int sta = n;

     for(int i = m; i >= 0; i--){

        for(int j = sta; j >= 0; j--){

            if(dp[j][i][1] == ans && ans){

                s.push(j);

                sta = j - 1;

                ans -= v[i][j];

                break;

            }

        }

    }

    while(!s.empty()){

        int res =s.top();

        s.pop();

        printf("%d ", res);

    }

    printf("\n");

    return 0;

}

巴特西

SGU 104 Little shop of flowers【DP】

题目链接：

题意：

分析：

代码：

最新文章

热门文章