标题叙述 Description,游戏的渴求是使您所得的k最大依然最小

拾8伍 数字娱乐

 

200三年NOIP全国际结盟赛普及组

 时限: 一s

 空间限制: 12九千KB

 标题等级 : 黄金
高尔德

 

 

题材叙述 Description

丁丁近年来沉迷于2个数字娱乐之中。那个游乐看似不难,但丁丁在商讨了很多天以往却发现原来在简短的平整下想要赢得那个游乐并不那么简单。游戏是这么的,在你前边有一圈整数(一共n个),你要按梯次将其分为m个部分,各部分内的数字相加,相加所得的m个结果对十取模后再相乘,最后获得七个数k。游戏的须求是使您所得的k最大依然最小。

比如说,对于上面那圈数字(n=4,m=②):

                                  2

                   4                           -1

                                 3

当供给最小值时,((二-壹) mod 10)×((4+三) mod
10)=一×七=七,需求最大值时,为((二+四+三) mod 10)×(-一 mod
十)=九×9=八一。特别值得注意的是,无论是负数依旧正数,对10取模的结果均为非负值。

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

输入描述 Input Description

输入文件首先行有七个整数,n(一≤n≤50)和m(一≤m≤九)。以下n行每行有个整数,其相对值不超越十4,按顺序给出圈中的数字,首尾相接。

出口描述 Output Description

输出文件有两行,各包罗1个非负整数。第三行是您程序获取的微小值,第三行是最大值。

样例输入 萨姆ple Input

4 2

4

3

-1

2

样例输出 Sample Output

7

81

数据范围及提醒 Data Size & Hint

en

f[i][j]=max(f[i][j],f[k][j-1]*(((sum[i]-sum[k])%10+10)%十))的意义是前k个数划分成j-壹份,所之前i个数划分成j份的最大值是k到i的和Mod10
* 前k个数划分成j-1份

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int sum[210],a[210];
 6 int f[210][20],g[210][10];
 7 int n,m,minn = 0x7f,maxn = 0;
 8 void dp(int num[])
 9 {
10     memset(f,0,sizeof(f));
11     memset(g,0x3f,sizeof(g));
12     for (int i=1; i<=n; ++i)    
13         sum[i] = sum[i-1]+num[i];    
14     for (int i=1; i<=n; ++i)
15         f[i][1] = g[i][1] = (sum[i]%10+10)%10;
16     for (int j=2; j<=m; ++j)
17         for (int i=j; i<=n; ++i)
18             for (int k=j-1; k<=i-1; ++k)
19             {
20                 f[i][j] = max(f[i][j],f[k][j-1]*(((sum[i]-sum[k])%10+10)%10));
21                 g[i][j] = min(g[i][j],g[k][j-1]*(((sum[i]-sum[k])%10+10)%10));
22             }
23     minn = min(minn,g[n][m]);
24     maxn = max(maxn,f[n][m]);
25 }
26 int main()
27 {
28     scanf("%d%d",&n,&m);
29     for (int i=1; i<=n; ++i)
30     {
31         scanf("%d",&a[i]);
32         a[i+n] = a[i];
33     }
34     for (int i=0; i<n; ++i)
35         dp(a+i);
36     printf("%d\n%d",minn,maxn);
37     return 0;
38 }

 

1085 数字娱乐

200三年NOIP全国际联盟赛普及组

日子范围: 1s    空间范围: 128000KB    标题等级 : 黄金
戈尔德

题材叙述 Description

丁丁近日沉迷于几个数字娱乐之中。这几个娱乐类似简单,但丁丁在商量了更仆难数天现在却发现原来在简单的平整下想要赢得这几个娱乐并不那么容易。游戏是那样的,在你前边有1圈整数(一共n个),你要按顺序将其分成m个部分,各部分内的数字相加,相加所得的m个结果对十取模后再相乘,最终赢得二个数k。游戏的渴求是使您所得的k最大依旧最小。

比如说,对于上边那圈数字(n=四,m=二):

         
                        2

                  
4                           -1

                                
3

当供给最小值时,((2-一)
mod 拾)×((四+三) mod 十)=一×7=7,须要最大值时,为((贰+4+三) mod 十)×(-一 mod
十)=九×九=81。越发值得注意的是,无论是负数照旧正数,对十取模的结果均为非负值。

丁丁请您编写程序帮他获得那么些娱乐。

输入描述 Input
Description

输入文件首先行有八个整数,n(一≤n≤50)和m(一≤m≤玖)。以下n行每行有个整数,其相对值不超过104,按顺序给出圈中的数字,首尾相接。

出口描述 Output
Description

输出文件有两行,各包罗一个非负整数。第二行是您程序得到的小不点儿值,第三行是最大值。

样例输入 Sample
Input

4
2

4

3

-1

2

样例输出 Sample
Output

7

81

数量范围及提醒 Data
Size & Hint

en

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=205;
 6 int Min,Max,n,sum[maxn],num[maxn],f[maxn][15],g[maxn][15],m;
 7 void DP(int a[]){
 8     for(int i=1;i<=n;i++)
 9       sum[i]=sum[i-1]+a[i];
10     for(int i=0;i<=n;i++)
11       for(int j=0;j<=m;j++)
12         f[i][j]=0,g[i][j]=0x5f;
13     for(int i=1;i<=n;i++)
14       f[i][1]=g[i][1]=(sum[i]%10+10)%10;
15     for(int j=2;j<=m;j++)
16       for(int i=j;i<=n;i++)
17         for(int k=j-1;k<=i-1;k++){
18             f[i][j]=max(f[i][j],f[k][j-1]*(((sum[i]-sum[k])%10+10)%10));
19             g[i][j]=min(g[i][j],g[k][j-1]*(((sum[i]-sum[k])%10+10)%10));
20         }
21     Min=min(Min,g[n][m]);
22     Max=max(Max,f[n][m]);
23 }
24 int main()
25 {
26     Min=0x5f;Max=0;
27     scanf("%d%d",&n,&m);
28     for(int i=1;i<=n;i++){
29         scanf("%d",&num[i]);
30         num[i+n]=num[i];
31     }
32     for(int i=0;i<n;i++)
33       DP(num+i);
34     printf("%d\n%d",Min,Max);
35     return 0;
36 }

思路:划分型DP+环形DP
 f[i][j]=max(f[i][j],f[k][j-1]*(((sum[i]-sum[k])%十+十)%10))的意思是前k个数划分成j-一份,所以前i个数划分成j份的最大值是k到i的和Mod十
* 前k个数划分成j-1份

相关文章

网站地图xml地图