poj 動態規劃DP

這道題目我一開始的思路是用二維DP，結果TLE了。後來換了個思路，終於AC了。

不需要判斷所有的情況，我們用dp[i]表示前i個牛圈中最大的牛數，而這個i首先必須>=限制的牛圈樹f。用num[i]表示dp[i]中包含了多少牛圈。

我們可以知道，dp[i] = sum[i] - sum[i-f])/f or dp[i-1] + data[i]， 前一個代表到i為止前f個牛圈的牛數，後一個代表前i-1個牛圈中最大牛數+第i個牛圈中的牛數。其實也就是到i為止前num[i-1]+1個牛圈的牛數。而判斷取哪個的條件是判斷(sum[i] - sum[i-f])）/f和dp[i-1] + data[i]/（num[i-1]+1）的大小。

#include
#include
#define max(x,y)(x>y?x:y)
#define MAX 100002
double dp[MAX],data[MAX],num[MAX],sum[MAX];
int main(){
	int i,n,f;
	double maxval;
	scanf("%d %d",&n,&f);
	for(i=1;i<=n;i++) {
		scanf("%lf",&data[i]);
		sum[i] = data[i] +sum[i-1];
		num[i] = f;
	}
	dp[f] = sum[f];
	maxval  = dp[f]*1000/f;
	for(i=f+1;i<=n;i++){
		if ((sum[i] - sum[i-f])/f > (dp[i-1] + data[i])/ (num[i-1] +1)){
			dp[i] = sum[i] - sum[i-f];
			num[i] = f;
		}
		else{
		dp[i] = dp[i-1] + data[i];
		num[i] = num[i-1] +1;
		}
		maxval = max(maxval,dp[i]*1000/num[i]);
	}
	
	printf("%d\n",(int)(maxval));
}