UVALive 5790 Ball Stacking DP

　　DP的方向真的很重要，这题做的时候死活想不出来，看了题解以后恍然大悟原来这么简单。

题意：

　　有n层堆成金字塔状的球，若你要选一个球，你必须把它上面那两个球取了，当然也可以一个不取。求选的球最大的权值和。

题解：

　　把原来的金字塔变换一下形式，转换成直角三角形的样子。

假如原三角形是这样的：

然后可以转化成这个样子：

这样子的话，要选择一个球，就要选择他左上的那个矩形。

这样就容易转移了，用dp[i][j]表示变换后的图形中，第 i 行取的最下面一个球是j，很明显这样下一行就只能小于j个球了。

不过，这样每层之间的转移是O(n^2)的，也许会T，然后可以用单调性来优化一下。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <string>

#include <queue>

#include <stack>

#include <vector>

#include <map>

#include <set>

#include <functional>

#include <cctype>

#include <time.h>

using namespace std;

const int INF = <<;

const int MAXN = ;

int a[MAXN][MAXN];

int sum[MAXN][MAXN];

int dp[MAXN][MAXN];

int n;

int main() {

    #ifdef Phantom01

        freopen("LA5790.txt", "r", stdin);

    #endif //Phantom01

    while (scanf("%d", &n)!=EOF) {

        if (n==) break;

        memset(dp, , sizeof(dp));

        memset(sum, , sizeof(sum));

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

            for (int j = ; j <= i; j++)

                scanf("%d", &a[i-j+][j]);

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

            for (int j = ; j <= n-i+; j++)

                 sum[i][j] = a[i][j] + sum[i][j-] + sum[i-][j] - sum[i-][j-];

        int ans = ;

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

            int best = n-i+;

            for (int j = n-i+; j > ; j--) {

                if (dp[i-][j]>dp[i-][best]) best = j;

                dp[i][j] =  dp[i-][best]+sum[i][j] - sum[i-][j];

                ans = max(ans, dp[i][j]);

            }

        }

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

    }

    return ;

}

巴特西

UVALive 5790 Ball Stacking DP

最新文章

热门文章