HDU 5291 Candy Distribution
Candy Distribution
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 544 Accepted Submission(s): 214
Problem Description
WY has n kind of candy, number 1-N, The i-th kind of candy has ai. WY would like to give some of the candy to his teammate Ecry and lasten. To be fair, he hopes that Ecry’s candies are as many as lasten's in the end. How many kinds of methods are there?
Input
The first line contains an integer T<=11 which is the number of test cases.
Then T cases follow. Each case contains two lines. The first line contains one integer n(1<=n<=200). The second line contains n integers ai(1<=ai<=200)
Output
For each test case, output a single integer (the number of ways that WY can distribute candies to his teammates, modulo 109+7 ) in a single line.
Sample Input
2 1 2 2 1 2
Sample Output
2 4
Hint
Sample: a total of 4, (1) Ecry and lasten are not assigned to the candy; (2) Ecry and lasten each to a second kind of candy; (3) Ecry points to one of the first kind of candy, lasten points to a second type of candy; (4) Ecry points to a second type of candy, lasten points to one of the first kind of candy.
Author
FZUACM
Source
2015 Multi-University Training Contest 1
- $定义dp[i]表示两人之间相差i个糖果的情况数$
- 当前有a个第i种糖果,那么我们有\[dp[j] = dp[j]\times (a/2 + 1) + dp[j-1]\times((a-1)/2+1)+dp[j+1]\times((a-1)/2+1)+\cdots + dp[j-a]\times ((a-a)/2 + 1) + dp[j+a]\times ((a-a)/2 + 1)\]
- $可以发现算出*dp[0]之后,算*dp[1] = *dp[0] + dp[1] + dp[3] - dp[0] - dp[-2]$
- $此时只要把[j+1,j+1+a]的奇数位置的dp值加起来 - [j-a,j]偶数位置的dp值 + *dp[0] = *dp[1]$
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = ;
const LL mod = ;
LL dp[maxn],sum[][maxn];
int bound[maxn],n;
int main(){
int kase;
scanf("%d",&kase);
while(kase--){
scanf("%d",&n);
int S = ;
for(int i = ; i <= n; ++i){
scanf("%d",bound + i);
S += bound[i];
}
if(S&) S |= ;
memset(dp,,sizeof dp);
memset(sum,,sizeof sum);
dp[S] = ;
for(int i = ,t = (S<<); i <= n; ++i){
sum[][] = dp[];
sum[][] = ;
for(int j = ; j <= t; ++j){
sum[][j] = sum[][j-];
sum[][j] = sum[][j-];
sum[j&][j] += dp[j];
sum[j&][j] %= mod;
}
LL ret = ;
for(int j = ; j <= bound[i]; ++j){
ret += (LL)dp[j]*(((bound[i] - j)>>) + );
ret %= mod;
}
for(int j = ,p = (bound[i]&^); j <= t; ++j){
dp[j] = ret;
int x = max(,j - bound[i] - );
ret += (sum[p][j + bound[i] + ] - sum[p][j]);
p ^= ;
ret -= sum[p][j] - sum[p][x];
ret %= mod;
}
}
printf("%I64d\n",(dp[S] + mod)%mod);
}
return ;
}
参考这位大大的博客
$dp[j-1]\times((a-1)/2+1)$就是表示先取第i种的一个给自己,剩下的两人均分,
但是,我们不一定要全部分,所以那个1就是表示剩下的不分了,为什么乘以$(a-1)/2$,因为两个人可以都分1,都分2,都分$(a-1)/2$,共$(a-1)/2$种
最新文章
- vim的配置与使用
- UWP开发之Mvvmlight实践一:如何在项目中添加使用Mvvmlight(图文详解)
- kail linux 虚拟机安装实录(一) 新建虚拟机
- block要掌握的东西
- 一、Hello World
- vimium: 浏览器神器
- groovy-实现接口
- Apche Kafka 的生与死 &ndash; failover 机制详解
- js基础之动画(一)
- 欧拉工程第55题:Lychrel numbers
- C#中的USB库 WinUSB
- Java_String_01_由转义字符串得到其原本字符串
- vue-cli axios跨域 + 反向代理模拟http请求host+referer
- Linux 同步时间 设置时区
- nexus-maven- repository-index.zip手动下载与设置
- Vue-学习。
- Scala的映射和元组操作
- 【CF472G】Design Tutorial: Increase the Constraints
- List多个字段标识过滤 IIS发布.net core mvc web站点 ASP.NET Core 实战:构建带有版本控制的 API 接口 ASP.NET Core 实战:使用 ASP.NET Core Web API 和 Vue.js 搭建前后端分离项目 Using AutoFac
- .NET可变性解析(协变和逆变)