学步园

贪心+DP，真是好巧妙啊，蒟蒻如何能想得出来TAT

因为red tower只对当前点有影响，所以应该放在最后。

dp[i][j]表示前i个Tower里有j个blue Tower，所以由point i是blue or green可以分成两种case

dp[i][j]=max((dp[i-1][j-1]+(i-j)*y*(t+(j-1)*z)),dp[i-1][j]+(i-j-1)*y*(t+j*z))

(i-j)*y*(t+(j-1)*z)表示前面i-j个green对point i的影响，(i-j-1)*y*(t+j*z)表示前面i-j-1个green对point i的影响.

damage=dp[i][j]+(n-i)*x*(t+j*z)+(n-i)*(i-j)*y*(t+j*z); (n-i)*x*(t+j*z)表示后n-i个red的影响，(n-i)*(i-j)*y*(t+j*z)表示前面的green对后n-i个point的影响
ans=max(ans,damage);

注意dp的时候i从1枚举，没有考虑全是red的情况，所以该case要特判。

WA了好久== 因为之前对状态没有考虑全，木有对每个disjoint condition都想清楚。比如dp[i][0],dp[i][i]这种。

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
#include<map>
#include<time.h>
using namespace std;
//hdu 4939

const int maxn=1510;
int T;
long long n;
long long x;
long long y;
long long z;
long long t;
long long dp[maxn][maxn];
long long ans;
void DP()
{
    memset(dp,0,sizeof(dp));
    ans=n*t*x;//因为i是从1开始枚举的，没有包括全是red的情形，所以要特判。
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=dp[i-1][0]+(i-1)*y*t;
        for(int  j=1;j<i;j++)
        {
            dp[i][j]=max((dp[i-1][j-1]+(i-j)*y*(t+(j-1)*z)),dp[i-1][j]+(i-j-1)*y*(t+j*z));
        }
        dp[i][i]=dp[i-1][i-1];
    }
    long long damage=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            damage=dp[i][j]+(n-i)*x*(t+j*z)+(n-i)*(i-j)*y*(t+j*z);
            ans=max(ans,damage);
        }
    }
}

int main()
{
    freopen("input.txt","r",stdin);
   //  freopen("data.txt","r",stdin);
    // freopen("out1.txt","w",stdout);
    scanf("%d",&T);
    for(int ca=1;ca<=T;ca++)
    {
        scanf("%I64d %I64d %I64d %I64d %I64d",&n,&x,&y,&z,&t);
        if(n==1)
        {
            ans=t*x;
        }
        else
        {
            DP();
        }
        printf("Case #%d: %I64d\n",ca,ans);
    }

    return 0;
}