#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