学步园

传送门：【HDU】4939 Stupid Tower Defense

题目分析：稍微分析一下就可以知道红塔放在前面一定不会比放在后面更优，然后我们只需要对绿塔和蓝塔做一次dp。设dp[ i ][ j ]为前i个塔中有j个绿塔造成的最大伤害。那么可以得到这样的转移方程：

FOR ( i , 1 , n )
		FOR ( j , 1 , i ) {
			dp[i][j] = dp[i - 1][j - 1] + ( t + ( i - j ) * z ) * ( j - 1 ) * y ;
			if ( i - 1 >= j ) dp[i][j] = max ( dp[i][j] , dp[i - 1][j] + ( t + ( i - j - 1 ) * z ) * j * y ) ;
		}

第一条表示第i个位置放绿塔，( t + ( i - j ) * z ) * ( j - 1 ) * y为所有塔对位置i造成的伤害。

第二条表示第i个位置放蓝塔，( t + ( i - j - 1 ) * z ) * j * y为所有塔对位置i造成的伤害。

做完这个dp以后我们枚举所有的情况[ i , j ]，对于[ i , j ]这种情况有：

damage[ i ][ j ]=dp[ i ][ j ] + ( n - i ) * ( ( t + ( i - j ) * z ) * ( x + j * y ) )的总伤害，( n - i ) * ( ( t + ( i - j ) * z ) * ( x + j * y ) )为x塔造成的伤害与前j个塔在之后造成的所有伤害的和。

答案即ans = max{damage[ i ][ j ] | 0 <= i <= n，0 <= j <= i }。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )

typedef long long LL ;

const int MAXN = 1505 ;

LL dp[MAXN][MAXN] ;
LL n , x , y , z , t ;

void solve () {
	scanf ( "%I64d%I64d%I64d%I64d%I64d" , &n , &x , &y , &z , &t ) ;
	FOR ( i , 1 , n )
		FOR ( j , 1 , i ) {
			dp[i][j] = dp[i - 1][j - 1] + ( t + ( i - j ) * z ) * ( j - 1 ) * y ;
			if ( i - 1 >= j ) dp[i][j] = max ( dp[i][j] , dp[i - 1][j] + ( t + ( i - j - 1 ) * z ) * j * y ) ;
		}
	LL ans = 0 ;
	FOR ( i , 0 , n )
		FOR ( j , 0 , i )
			ans = max ( ans , dp[i][j] + ( n - i ) * ( ( t + ( i - j ) * z ) * ( x + j * y ) ) ) ;
	printf ( "%I64d\n" , ans ) ;
}

int main () {
	int T , cas = 0 ;
	scanf ( "%d" , &T ) ;
	while ( T -- ) {
		printf ( "Case #%d: " , ++ cas ) ;
		solve () ;
	}
	return 0 ;
}