洛谷P1043 数字游戏

2018-06-17 21:30:06来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共n个),你要按顺序将其分为m个部分,各部分内的数字相加,相加所得的m个结果对10取模后再相乘,最终得到一个数k。游戏的要求是使你所得的k最大或者最小。

例如,对于下面这圈数字(n=4,m=2):

要求最小值时,((2-1) mod 10)×((4+3) mod 10)=1×7=7,要求最大值时,为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是,无论是负数还是正数,对10取模的结果均为非负值。

丁丁请你编写程序帮他赢得这个游戏。

输入输出格式

输入格式:

 

输入文件第一行有两个整数,n(1≤n≤50)和m(1≤m≤9)。以下n行每行有个整数,其绝对值不大于104,按顺序给出圈中的数字,首尾相接。

 

输出格式:

 

输出文件有两行,各包含一个非负整数。第一行是你程序得到的最小值,第二行是最大值。

 

输入输出样例

输入样例#1: 复制
4 2
4
3
-1
2
输出样例#1: 复制
7
81

 

$DpMin[i][j][k]$表示$i$到$j$中切了$k$次的最小值

$DpMax$表示最大值

转移的时候枚举断点

左右两边相乘

 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2001;
const int INF=0x7fffff;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
int DpMin[101][101][11];
int DpMax[101][101][11];
int a[MAXN];
int Query(int a)
{
    return ((a%10)+10)%10;
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    int n=read(),m=read();
    for(int i=1;i<=n;i++)   a[i]=read(),a[i+n]=a[i];
    for(int i=1;i<=2*n;i++) a[i]+=a[i-1];
    
    for(int l=1;l<=2*n;l++)
      for(int r=l;r<=2*n;r++)
        DpMin[l][r][1]=DpMax[l][r][1]=Query(a[r]-a[l-1]);
            
    for(int i=2;i<=m;i++)
      for(int l=1;l<=2*n;l++)
        for(int r=l+i-1;r<=2*n;r++)
          DpMin[l][r][i]=INF;
    for(int i=2;i<=m;i++)//已经切了k次
        for(int l=1;l<=2*n;l++)
            for(int r=l+i-1;r<=2*n;r++)
                for(int k=l+i-2;k<r;k++)
                {
                    DpMin[l][r][i]=min(DpMin[l][r][i],DpMin[l][k][i-1]*Query(a[r]-a[k]));
                    DpMax[l][r][i]=max(DpMax[l][r][i],DpMax[l][k][i-1]*Query(a[r]-a[k]));
                }
    int AnsMax=0,AnsMin=INF;
    for(int i=1;i<=n;i++)
        AnsMax=max(AnsMax,DpMax[i][i+n-1][m]),
        AnsMin=min(AnsMin,DpMin[i][i+n-1][m]);
    printf("%d\n%d",AnsMin,AnsMax);
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:应用结构体完成结构体的输出

下一篇:字符串与指针