首页 > 代码库 > 数字游戏(两个大神写得)
数字游戏(两个大神写得)
Description
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共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取模的结果均为非负值。丁丁请你编写程序帮他赢得这个游戏。
Input
多个测试案例，处理到文件末尾，每个测试第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。
Output
每个测试案例输出有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。
Sample Input
4 243-12
Sample Output
781C:
1 #include<stdio.h> 2 #include<string.h> 3 #define INF 1<<30 4 int a[120],s[120],m,n; 5 int dp1[120][15],dp2[120][15]; 6 int maxn,minn; 7 inline int max(int a,int b) 8 { 9 return a>b?a:b;10 }11 inline int min(int a,int b)12 {13 return a<b?a:b;14 }15 int main()16 {17 //freopen("a.txt","r",stdin);18 int i,j,k,l,tmp;19 while(scanf("%d %d",&m,&n)==2)20 {21 for(i=1;i<=m;i++)22 {23 scanf("%d",&a[i]);24 a[m+i]=a[i];25 }26 s[0]=0;27 for(i=1;i<=2*m;i++)28 {29 s[i]=s[i-1]+a[i];30 }31 maxn=-INF,minn=INF;32 for(l=1;l<=m;l++)33 {34 for(i=1;i<=2*m;i++)35 for(j=1;j<=n;j++)36 {37 dp1[i][j]=INF;38 dp2[i][j]=-INF;39 }40 for(i=l;i<=m+l-1;i++)41 {42 tmp=(s[i]-s[l-1])%10;43 if(tmp<0) tmp+=10;44 dp1[i][1]=tmp;dp2[i][1]=dp1[i][1];45 }46 for(j=2;j<=n;j++)47 for(i=j+l-1;i<=m+l-1;i++)48 for(k=j+l-2;k<i;k++)49 {50 tmp=(s[i]-s[k])%10;51 if(tmp<0) tmp+=10;52 dp1[i][j]=min(dp1[i][j],dp1[k][j-1]*tmp);53 dp2[i][j]=max(dp2[i][j],dp2[k][j-1]*tmp);54 }55 minn=min(dp1[l+m-1][n],minn);56 maxn=max(dp2[l+m-1][n],maxn);57 }58 printf("%d\n%d\n",minn,maxn);59 }60 return 0;61 }
C++:
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 int n,m,Max,Min,s[55],d[55][10],dp[55][10]; 6 void DP(int a[]) 7 { 8 int i,j,k; 9 for(i=1;i<=n;i++)10 s[i]=s[i-1]+a[i];11 for(i=0;i<=n;i++)12 for(j=0;j<=m;j++)13 {14 d[i][j]=0;15 dp[i][j]=-1u>>1;16 }17 d[0][0]=dp[0][0]=1;18 for(i=1;i<=n;i++)19 d[i][1]=dp[i][1]=(s[i]%10+10)%10;20 for(j=2;j<=m;j++)21 for(i=j;i<=n;i++)22 for(k=j-1;k<i;k++)23 {24 d[i][j]=max(d[i][j],d[k][j-1]*(((s[i]-s[k])%10+10)%10));//第k+1个数到第i个数分到第j部分25 dp[i][j]=min(dp[i][j],dp[k][j-1]*(((s[i]-s[k])%10+10)%10));26 }27 Max=max(Max,d[n][m]);28 Min=min(Min,dp[n][m]);29 }30 int main()31 {32 // freopen("a.txt","r",stdin);33 while(scanf("%d%d",&n,&m)==2)34 {35 int i,j,a[105];36 Max=0;37 Min=-1u>>1;38 for(i=1;i<=n;i++)39 {40 scanf("%d",a+i);41 a[n+i]=a[i];42 }43 for(j=0;j<n;j++)44 DP(a+j);45 printf("%d\n%d\n",Min,Max);46 }47 }
数字游戏(两个大神写得)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。