POJ 3186 Treats for the Cows ——（DP）

　　第一眼感觉是贪心，，果断WA。然后又设计了一个两个方向的dp方法，虽然觉得有点不对，但是过了样例，交了一发，还是WA，不知道为什么不对= =，感觉是dp的挺有道理的，，代码如下（WA的）：

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 2000 + 5;

int a[N];
int dp[N][N];
int n;

int getDay(int i,int j)
{
    return n - (j - i) + 1;
}

int main()
{
    while(scanf("%d",&n) == 1)
    {
        for(int i=1;i<=n;i++) scanf("%d",a+i);
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n+1;j++) dp[i][j] = max(dp[i][j], dp[i-1][j] + getDay(i,j) * a[i]);
        }
        for(int j=n+1;j>=1;j--)
        {
            for(int i=j-1;i>=0;i--) dp[i][j] = max(dp[i][j], dp[i][j+1] + getDay(i,j) * a[j]);
        }
        int ans = 0;
        for(int i=0;i<=n;i++) ans = max(ans, dp[i][i+1]);
        printf("%d
",ans);
    }
    return 0;
}

　　看了别人的博客以后，有一个不错的dp方法：dp[i][j]表示左边已经选了i个右边已经选了j个最大值，然后转移也很明显。AC代码如下：

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 2000 + 5;

int a[N];
int dp[N][N];
int n;

int main()
{
    while(scanf("%d",&n) == 1)
    {
        for(int i=1;i<=n;i++) scanf("%d",a+i);
        memset(dp,0,sizeof dp);
        for(int i=0;i<=n;i++)
        {
            for(int j=0;i+j<=n;j++)
            {
                if(i > 0) dp[i][j] = max(dp[i][j], dp[i-1][j] + a[i] * (i+j));
                if(j > 0) dp[i][j] = max(dp[i][j], dp[i][j-1] + a[n-j+1] * (i+j));
            }
        }
        int ans = 0;
        for(int i=0;i<=n;i++) ans = max(ans, dp[i][n-i]);
        printf("%d
",ans);
    }
    return 0;
}