小智的糖果(Candy) 51nod 提高组试题
题目描述
小智家里来了很多的朋友,总共有N个人,站成一排,分别编号为0到N-1,小智要给他们分糖果。但 是有的朋友有一些特殊的要求,有的人要求他左右的两个人(左边一个、右边一个,一共2个人)的 糖果数都比他的多,有的人要求他左右的两个人的糖果数都比他的少。同时小智希望给不同的人分到 的糖果数不相同,并且每个人至少有一个糖果,同时小智希望分出的糖果个数尽可能的少,现在小智 想知道有多少种分糖果的方法。数据保证不会出现两个人的要求产生冲突的情况。
输入格式
第一行三个数N,M,K,分别表示人数,第一种要求的人的个数,K表示第二种要求的人的个数。 接下来M行,每行一个数x,表示位置x的人要求他左右两个人的糖果数都比他的多 接下来K行,每行一个数y,表示位置y的人要求他左右两个人的糖果数都比他的少
输出格式
输出一个数表示方法数对 1000000007取模的结果。
这道题考虑Dp解法。
如何想到用DP解法? 因为题目中要求我们最多有多少种方法,如果一个个枚举或者求出的话,就会让我们的时间复杂度分分钟上去。因此这类题都是套路一般的DP。
首先,看到题目中有两种要求。一种是让两边的小,一种是让两边的大。
这种要求有一点不好处理的就是,我们总是喜欢直接查看每一个点的情况,而不是查看其旁边的点情况,这样很不方便。于是我们转换一下。
设flagi = 1时,表示第 i 个点小于前一个点。同样的,当 flagi = 2时,表示第i个点大于前一个点。当然,falg = 0时,表示无特殊关系。
然后,设置一个dp[i][j] 表示由前 i 个数组成的序列且第 i 位为 j 的合法情况数。在规划的过程中,针对不同的 flag[i],对应不同的状态转移,这里涉及到一个最后一位数 j 插入序列的思维,可以看做把前边的每一种排列中大于等于 j 的数 ++,也就可以达到空出 j 这个数将其插入的效果。
在这里引入一个 sum[j],表示为前一轮状态下,最后一位小于等于 j 的情况的和。也就是说,当规划到第 i 位时,sum[j] 表示前 i - 1 位数组成的序列的合法情况的 dp[i - 1][j] 的前缀和。
到这里,这道题也就可以被我们AC了。我们要求的和就是 sum[n].
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define N 100100
#define isdigit(c) ((c)>='0'&&(c)<='9')
const int mod = (int)1e9 + ; inline int read(){
int x = , s = ;
char c = getchar();
while(!isdigit(c)){
if(c == '-')s = -;
c = getchar();
}
while(isdigit(c)){
x = (x << ) + (x << ) + (c ^ '');
c = getchar();
}
return x * s;
} int flag[N], sum[N], dp[N];
int main(){
// freopen("candy.in","r",stdin);
// freopen("candy.out","w",stdout);
int n = read(), K = read(), M = read();
for(int i = ;i <= K; i++){
int a = read();
flag[++a] = ;
flag[a + ] = ;
}
for(int i = ;i <= M; i++){
int a = read();
flag[++a] = ;
flag[a + ] = ;
}
dp[] = sum[] = ;
for(int i = ;i <= n; i++){
for(int j = ;j <= i; j++){
if(flag[i] == ){
dp[j] = sum[i - ] % mod;
}
else if(flag[i] == ){
dp[j] = (sum[i - ] - sum[j - ] + mod) % mod;
}
else{
dp[j] = sum[j - ];
}
}
for(int j = ;j <= i; j++){
sum[j] = (sum[j - ] + dp[j]) % mod;
}
}
cout << sum[n] << endl;
return ;
}
最新文章
- 【原创】自己动手写工具----签到器[Beta 2.0]
- VB下对HTML元素的操作
- 地图定位IOS8.0之前的定位
- HTTP常见状态码 200 301 302 404 500
- Iterator
- (转)Android: NDK编程入门笔记
- C-Free 您不能使用调试解决方案
- vue中数据双向绑定注意点
- 1.JavaScript 教程:基础语法
- Docker容器中开始.Net Core之路
- Macbook pro开启允许任何源
- box-shadow 边框阴影
- 运行成功的Demo(Python+Appium)
- COCOMOII
- 转)安装svn服务器
- 自动化部署MySQL 5.6 步骤 制作到ftp共享,永远使用
- 二、ionic如何使用外链
- 《阿里巴巴JAVA开发手册》里面写超过三张表禁止join这是为什么?
- 几个与JVM相关的JDK工具:jps, jstat, jmap
- Vue前端数据采集 埋点 追踪用户系列行为
热门文章
- CodeForces - 1245 B - Restricted RPS(贪心)
- HDU - 6187 (最大生成树) 最小生成树
- 算法——Java实现栈
- zabbix 告警信息与恢复信息
- Django 设置admin后台表和App(应用)为中文名
- 【x64软路由】OpenWrt(LEDE) 20200329编译 反追踪 抗污染 加速 PSW 无缝集成 UPnP NAS
- vue项目中使用bpmn-自定义platter
- Autojs - 用 JavaScript 实现自己的安卓手机自动化工具脚本
- GIT代码版本管理
- Spring Boot定时任务运行一段时间后自动关闭的解决办法