洛谷——P1043 数字游戏
2024-09-26 23:14:26
https://www.luogu.org/problem/show?pid=1043
题目描述
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共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 环->破换成链。
f[i][j][k] 表示 在[i,j]区间内 化成 h个部分 的最值
求出前缀和 枚举h,左右端点以及断点-->>f[i][j][h]=(f[i][k-1][h-1]*(sum[j]-sum[k-1])
#include <cstdio> #define INF (1e7)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b) using namespace std; const int N();
int n,m,num[N],sum[N];
int f_min[N][N][],f_max[N][N][],maxn,minn=INF; int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",num+i),num[i+n]=num[i];
for(int i=;i<=(n<<);i++)
sum[i]+=sum[i-]+num[i];
for(int i=;i<=(n<<);i++)
for(int j=i;j<=(n<<);j++)
for(int k=;k<=m;k++)
{
if(k==)
{
f_min[i][j][k]=((f_min[i][j-][k]+num[j])%+)%;
f_max[i][j][k]=((f_max[i][j-][k]+num[j])%+)%;
}
else f_min[i][j][k]=INF;
}
for(int h=;h<=m;h++)
for(int i=;i<=(n<<);i++)
for(int j=h+i-;j<=(n<<);j++)
for(int k=h+i-;k<=j;k++)
{
f_min[i][j][h]=min(f_min[i][j][h],f_min[i][k-][h-]*(((sum[j]-sum[k-])%+)%));
f_max[i][j][h]=max(f_max[i][j][h],f_max[i][k-][h-]*(((sum[j]-sum[k-])%+)%));
}
for(int i=;i<=n;i++)
{
minn=min(minn,f_min[i][i+n-][m]);
maxn=max(maxn,f_max[i][i+n-][m]);
}
printf("%d\n%d\n",minn,maxn);
return ;
}
最新文章
- Python_Day9_Socket编程
- TabControl控件的DrawItem事件怎么注册
- UITabBarController的创建等基本方法
- MongoDB ObjectId
- Leetcode: Majority Element II
- 正则表达式(/[^0-9]/g,&#39;&#39;)中的";/g";是什么意思 ?
- how-to-install-hyper-v-on-a-virtual-machine-in-hyper-v.aspx
- shell编程之数组和关联数组
- java反射案例讲解
- 进程控制之waitid函数
- Java和Tomcat类加载机制
- html幻灯效果页面
- openstack之网络基础
- 超简单的php缓存类
- Django rest framework(7)----分页
- Composer更新慢的解决方案
- Document.write和 getElementById(ID)
- LightOJ 1030 【概率DP求期望】
- jQuery 效果函数,jquery文档操作,jQuery属性操作方法,jQuerycss操作函数,jQuery参考手册-事件,jQuery选择器
- IIS 配置网站
热门文章
- Linux下安装过程中编译PHP时报错:configure: error: libjpeg.(a|so) not found
- 51nod-1189: 阶乘分数
- JNI 资源释放
- Oozie框架基础
- iOS菜鸟成长笔记(2)——网易彩票练习
- Unified BeginFrame scheduling for Chrome
- 给 “rm” 命令添加个“垃圾桶”
- [USACO16FEB]围栏Fenced In Platinum
- 如何解决本地仓库和远程仓库的冲突(Conflict)
- [JLOI2015]装备购买(线性基)