code1085 数字游戏

划分dp

把环变链（读入4 3 -1 2变成4 3 -1 2 4 3 -1 2）

设dp[i][j][k]为把i~j分成k份，各部分内的数字相加，相加所得的k个结果对10取模后再相乘，最终得到的一个数，这个数的最大或最小值。

dp[i][j][k]=max/min{dp[i][p][k-1]+func(p+1,j)}

i+k-2<=p<=j-1　　func(i,j)=(sum(i,j)%10+10)%10

(注意有负数取余，这样写：(x%10+10)%10 )

边界：dp[i][j][1]=func(i,j)

答案：max/min(dp[i][i+n-1][m]) i=1 to n+1

代码如下：

#include<iostream>

#define Max_n 55

#define Max_m 15

#define Max_int 1000000000

using namespace std;

int dp1[Max_n*][Max_n*][Max_m];

int dp2[Max_n*][Max_n*][Max_m];

int a[Max_n*];

int s[Max_n*];

int n,m;

inline int sum(int l,int r){ return s[r]-s[l-]; }

inline int func(int l,int r){ return (sum(l,r)%+)%; } 

int main(){

    cin>>n>>m;

    for(int i=;i<=n;i++){

        cin>>a[i];

        a[i+n]=a[i];

    }

    s[]=;

    for(int i=;i<=n*;i++){

        s[i]=s[i-]+a[i];

    }

    for(int i=;i<=n*;i++){

        for(int j=i;j<=n*;j++){//边界

            dp1[i][j][]=dp2[i][j][]=func(i,j);

        }

    }

    for(int i=;i<=n*;i++){

        for(int j=i;j<=n*;j++){

            for(int k=;k<=m;k++){

                dp1[i][j][k]=-Max_int;

                dp2[i][j][k]=Max_int;

                for(int p=i+k-;p<=j-;p++){

                    dp1[i][j][k]=max(dp1[i][j][k], dp1[i][p][k-]*func(p+,j));

                    dp2[i][j][k]=min(dp2[i][j][k], dp2[i][p][k-]*func(p+,j));

                }

            }

        }

    }

    int ans1=-Max_int;

    int ans2=Max_int;

    for(int i=;i<=n+;i++){

        ans1=max(ans1,dp1[i][i+n-][m]);

        ans2=min(ans2,dp2[i][i+n-][m]);

    }

    cout<<ans2<<endl<<ans1<<endl;

    return ;

}

巴特西

code1085 数字游戏

最新文章

热门文章