有哪些信誉好的足球投注网站- 1、本文档共8页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
ACM之经典题目
数字游戏——经典动态规划
2、问题分析
首先n个数在一个环上，要把这个环分成m部分，所以我们先要用一个数组来表示环，S[i]表示环(1＝＜i＝＜2*n),且有S[i]=S[n+i],用SUM[i]表示前i个数的和，则SUM[1]=S[1],SUM[i]=SUM[i-1]+S[i],其中不2=i2*n。
MAXD[i][j]表示把前i个数分成j部分得到最大值的最优解，则我们可以得递推公式
MAXD[i][j]=max{MAXD[k][j-1]*(((SUM[i]-SUM[k])%10+10)%10)}(j-1=ki)
同理我们用MIND[i][j]表示把前i个数分成j部分得到最小值的最优解，递推公式为
MIND[i][j]=min{MIND[k][j-1]*(((SUM[i]-SUM[k])%10+10)%10)}(j-1=ki)
代码实现如下：
#includeiostream
#includecstdlib
#includecmath
using namespace std;
int s[101];
int sum[51];
int maxd[51][31];
int mind[51][31];
int solve_max(int n,int m)
{
int i,j,k,max,maxx;
for(i=1;i=n;i++)
{
maxd[i][1]=(sum[i]%10+10)%10;
}
for(j=2;j=m;j++)
for(i=j;i=n;i++)
{
max=0;
for(k=j-1;ki;k++)
{
maxx=maxd[k][j-1]*(((sum[i]-sum[k])%10+10)%10);
if(maxmaxx)
max=maxx;
}
maxd[i][j]=max;
}
return maxd[n][m];
}
int solve_min(int n,int m)
{
int i,j,k,minx,min;
for(i=1;i=n;i++)
{
mind[i][1]=(sum[i]%10+10)%10;
}
for(j=2;j=m;j++)
for(i=j;i=n;i++)
{
min=INT_MAX;
for(k=j-1;ki;k++)
{
minx=mind[k][j-1]*(((sum[i]-sum[k])%10+10)%10);
if(minminx)
min=minx;
}
mind[i][j]=min;
}
return mind[n][m];
}
int main()
{
int n,m,i,j,max=0,min=INT_MAX;
scanf(%d%d,n,m);
for(i=1;i=n;i++)
{
scanf(%d,s[i]);
s[i+n]=s[i];
}
for(i=1;i=n;i++)
{
sum[1]=s[i];
for(j=i+1;jn+i;j++)
sum[j-i+1]=sum[j-i]+s[j];
int a=solve_max(n,m);
int b=solve_min(n,m);
if(maxa)
max=a;
if(minb)
min=b;
}
printf(%d%\n%d\n,min,max);
system(pause);
return 0;
}
二,1062---Trees Made to Order
分析：本题主要是求给定的N个结点能表示的数是多少，求到这个数后面就好求了，代码如下：
#includeiostream
#includecstdlib
using namespace std;
long full[19];
void printTree(int node,long num)
{
if(node==1)
{
printf(X);
return ;
}
int
文档评论（0）