P2858 [USACO06FEB]Treats for the Cows G/S 区间DP

(1) dfs 两个方向，(l+1,r ) (l,r-1)
(2)记忆化dfs 用f[l][r] = max(Ldfs,Rdfs);return f[l][[r]; 以l,r为状态
(3)推出DP状态转移方程
初始化 f[i][i] = n * a[i] //沿着dfs
f[l][r] = max(f[l+1][r] + a[i]*(n-i+1), f[l][r-1] + a[i] * (n-i+1));
这是一到区间DP,很多初学者会枚举区间开头和结尾来DP,但这是错的,应当先枚举区间长度,再枚举区间的开头,然后可以直接推出区间的结尾。
区间DP，为保证子问题被计算过，应该以区间长度为阶段
通过实验表明如果以开头和结尾来DP，则需要子问题的解时，子问题可能还未被解决
即计算顺序不同，按长度来DP则可以得到正确的顺序，能保证子问题被计算过

解法1 dfs 会发现有很多重复的状态

#define _CRT_SECURE_NO_WARNINGS
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int a[2005];
int ans = -inf;
void dfs(int l, int r, int d, int sum)
{
    if (l > r)
    {
        ans = max(ans, sum);
        return;
    }
    dfs(l + 1, r, d + 1, sum + a[l] * d);
    dfs(l, r - 1, d + 1,sum + a[r] * d);
}
int main()
{
    int n;
    cin >> n;
    int i;
    for (i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    dfs(1, n, 1, 0);
    cout << ans;
    return 0;
}

解法2 运用数组dp[l][r] 来记忆搜索状态表示区间l,r能得到的最多钱

#define _CRT_SECURE_NO_WARNINGS
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int a[2005];
int ans = -inf;
int dp[2005][2005];
int dfs(int l, int r, int d)
{
    if (dp[l][r])
    {
        return dp[l][r];
    }
    if (l > r)
    {
        return 0;
    }
    dp[l][r] = max(dfs(l + 1, r, d + 1) + a[l]*d, dfs(l, r - 1, d + 1)+a[r]*d);
    return dp[l][r];
}
int main()
{
    int n;
    cin >> n;
    int i;
    for (i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    cout << dfs(1, n, 1);
    return 0;
}

解法3 转化为递推也就是区间DP

状态转移方程

这是一道区间DP,很多初学者会枚举区间开头和结尾来DP,但这是错的,应当先枚举区间长度,再枚举区间的开头,然后可以直接推出区间的结尾。
区间DP，为保证子问题被计算过，应该以区间长度为阶段
通过实验表明，如果以开头和结尾来DP，则需要子问题的解时，子问题可能还未被解决
即计算顺序不同，按长度来DP则可以得到正确的顺序，能保证子问题被计算过

通过上述的DFS也可知是长度为1的区间推出长度为2的区间，故递推步骤不能错

dp[l][r] = max(dp[l+1][r] + d*a[l],dp[l][r] + d*a[r]);

#define _CRT_SECURE_NO_WARNINGS
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int a[2005];
int ans = -inf;
int dp[2005][2005];
int dfs(int l, int r, int d)
{
    if (dp[l][r])
    {
        return dp[l][r];
    }
    if (l > r)
    {
        return 0;
    }
    dp[l][r] = max(dfs(l + 1, r, d + 1) + a[l]*d, dfs(l, r - 1, d + 1)+a[r]*d);
    return dp[l][r];
}
int main()
{
    int n;
    cin >> n;
    int i;
    for (i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    cout << dfs(1, n, 1);
    return 0;
}