プロジェクトオイラー問149

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20149
簡単な動的計画法で十分間に合います。


#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm> 

__int64 dp[3][2001];
__int64 MOD=1000000;
__int64 DELL=500000;
__int64 ms[2001];
 
int main(){
 	__int64 sk[56],sum,ans;
	
	for(int i=1;i<=2000;i++){
 		int p=i%55;
		if(p==0){
			p=55;
			
 		}
		
 		if(i<=55){
			__int64 k=i;
			sk[i]=(100003-200003*k+300007*k*k*k)%MOD-DELL; 
 		}else{
			int p2=(p+55-24)%55;
			if(p2==0)p2=55;
 			sk[p]=(sk[p2]+sk[p]+MOD)%MOD-DELL;
		}
		if(i==1){
 			sum=sk[i];
			ans=sum;
		}else{
			if(0>=sum){
				sum=sk[p];
			}else{
				sum+=sk[p];
			}
 			ans=std::max(sum,ans);
		}
		dp[0][i]=sk[p];//左上
		dp[1][i]=sk[p];//上
		dp[2][i]=sk[p];//右上
	}
	int p1=2001;
	for(int i=2;i<=2000;i++){
		__int64 sum=0;
		__int64 dp2[3][2001];
		for(int j=1;j<=2000;j++){
			int p2=p1%55;
			if(p2==0)p2=55;
			int p3=(p1-24)%55;
			if(p3==0)p3=55;
			
			sk[p2]=(sk[p3]+sk[p2]+MOD)%MOD-DELL;

			//横
			sum=std::max(sk[p2],sk[p2]+sum);
			ans=std::max(sum,ans);
			
			//左上
			if(j>1){
				dp2[0][j]=std::max(dp[0][j-1]+sk[p2],sk[p2]);
			}else{
				dp2[0][j]=sk[p2];
				
			}
			ans=std::max(dp2[0][j],ans);
			//上
			dp2[1][j]=std::max(dp[1][j]+sk[p2],sk[p2]);
			ans=std::max(dp2[1][j],ans);
			
			//右上
			if(j<2000){
				dp2[2][j]=std::max(dp[2][j+1]+sk[p2],sk[p2]);
			}else{
				dp2[2][j]=sk[p2];			
			}
			ans=std::max(dp2[2][j],ans);
			p1++;
		}
		memcpy(dp,dp2,sizeof(dp2));
	}
	std::cout<<"ans="<<ans<<"\n";
}
最終更新:2015年12月14日 15:06