codevs 1085 数字游戏 dp或者暴搜
2024-08-26 13:47:50
1085 数字游戏
2003年NOIP全国联赛普及组
时间限制: 1 s
空间限制: 128000 KB
题目描述 Description
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共n个),你要按顺序将其分为m个部分,各部分内的数字相加,相加所得的m个结果对10取模后再相乘,最终得到一个数k。游戏的要求是使你所得的k最大或者最小。
例如,对于下面这圈数字(n=4,m=2):
2
4 -1
3
当要求最小值时,((2-1) mod 10)×((4+3) mod 10)=1×7=7,要求最大值时,为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是,无论是负数还是正数,对10取模的结果均为非负值。
丁丁请你编写程序帮他赢得这个游戏。
输入描述 Input Description
输入文件第一行有两个整数,n(1≤n≤50)和m(1≤m≤9)。以下n行每行有个整数,其绝对值不大于104,按顺序给出圈中的数字,首尾相接。
输出描述 Output Description
输出文件有两行,各包含一个非负整数。第一行是你程序得到的最小值,第二行是最大值。
样例输入 Sample Input
4 2
4
3
-1
2
样例输出 Sample Output
7
81
数据范围及提示 Data Size & Hint
en
思路:
dp:dp[i][j]=sigma(dp[i-j][t]) 1<=t<=i-j;
#include<bits/stdc++.h>
using namespace std;
#define ll __int64
#define mod 1000000007
#define pi (4*atan(1.0))
const int N=1e3+,M=1e6+,inf=1e9+;
int dp[N][N],n,m;
int dfs(int x,int y,int pre)
{
if(x<pre)
return ;
if(y==)
return ;
int sum=;
for(int i=max(,pre);i<=x;i++)
sum+=dfs(x-i,y-,i);
return sum;
}
int main()
{
int x,y,z,i,t;
scanf("%d%d",&x,&y);
printf("%d\n",dfs(x,y,));
return ;
}
暴力代码
最新文章
- 【原】AFNetworking源码阅读(一)
- Spket在Eclipse下的安装和配置(图文教程)
- Extjs4.0以上版本智能提示的方法
- JSON学习之二
- Auto Mapper04(MVC中的配置)
- 20145212 《Java程序设计》第7周学习总结
- (转)js函数参数设置默认值
- POJ 1159 - Palindrome (LCS, 滚动数组)
- Windows 系统消息范围和前缀,以及消息大全
- Bootstrap学习 - 组件
- Android Static分析
- Java Web高级编程(一)
- 使用fiddler修改支付金额,支付必测
- 抄一篇maven的备忘
- CentOS7.5 防火墙指令
- 小K(wifi)插座剖解
- 工具-VIM配置
- selenium + python 怎样才能滚到页面的底部?
- 【转载】Gradle构建多模块项目
- PetaPoco轻量级ORM框架 - Database API 手册
热门文章
- MYSQL--表分区、查看分区(转)
- Android Studio 使用小技巧和快捷键
- codechef : Marbles 题解
- Linux常见系统命令与文件操作
- 闪回事务(Flashback Transaction)
- 在PL/SQL中如何让程序暂停几秒钟
- django内置 Contenttypes 框架
- php等守护进程监控脚本(转载 http://www.9958.pw/post/php_script_scan)
- Jenkins系统+独立部署系统
- JVM类加载机制(转)