poj 3046 Ant Counting (DP多重背包变形)
2024-10-14 13:54:15
题目:http://poj.org/problem?id=3046
思路: dp [i] [j] :=前i种 构成个数为j的方法数。
#include <cstdio>
#include <cstring>
#include <iostream>
int T,A,S,B;
int hash[1010];
int dp[1010][10100]; const int MOD=1e6;
using namespace std;
int main(){ while(cin>>T>>A>>S>>B){
memset(hash,0,sizeof(hash));
for(int i = 1; i <= A; i++){
int u;
cin>>u;
hash[u]++;
}
memset(dp,0,sizeof(dp));
for(int i = 0; i <= hash[1]; i++) dp[1][i] = 1;//第一种取1~k
for(int i = 2; i <= T; i++)
for(int j = 0; j <= B; j ++){
for(int k = 0; k <= hash[i]; k++)
if(j >= k) {
dp[i][j] += dp[i-1][j-k];
dp[i][j] %= MOD;
}else break;
}
int sum = 0;
for(int i = S; i <= B; i++){
sum+= dp[T][i];
sum %= MOD;
}
cout<<sum<<endl;
}
return 0;
}
最新文章
- NTFS交换数据流隐写的应用
- 【BZOJ-1864】三色二叉树 树形DP
- C# 跨线程访问或者设置UI线程控件的方法
- 【Maximum Depth of Binary Tree 】cpp
- Android 小闹钟程序
- oc随笔二:组合、继承
- 实例学习SSIS(一)--制作一个简单的ETL包
- 谷歌浏览器js debug
- memcache细节解析
- JAVANIO通道
- 用于水和水蒸汽物性计算的Python模块——iapws
- 【A tour of go】练习题
- linux驱动编写之poll机制
- HTML中元素的position属性详解
- socketv 验证客户端链接的合法性
- Sublime Text 之运行 js 方法[2015-5-6更新mac下执行js]
- git忽略已添加版本控制的文件
- 20145118《Java程序设计》 第8周学习总结
- C语言初始化
- 二分求幂,快速求解a的b次幂