[USACO09MAR] Cow Frisbee Team S
题目描述
老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 $N$ 头奶牛中选出一支队伍。
每只奶牛的能力为整数，第 $i$ 头奶牛的能力为$R_i$ 。飞盘队的队员数量不能少于 $1$、大于$N$。一支队伍的总能力就是所有队员能力的总和。
约翰比较迷信，他的幸运数字是 $F$ ，所以他要求队伍的总能力必须是 $F$ 的倍数。请帮他
算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 $10^8$ 取模的值。
输入格式
第一行：两个用空格分开的整数：$N$ 和 $F$。
第二行到 $N+1$ 行：第 $i+1$ 行有一个整数$R_i$ ，表示第 $i$ 头奶牛的能力。
输出格式
第一行：单个整数，表示方案数对 $10^8$ 取模的值。
样例 #1
样例输入 #1
样例输出 #1
提示
数据范围与约定
- 对于 $100\%$ 的数据，$1 \le N \le 2000$，$1 \le F \le 1000$ ，$1 \le R_i \le 10^5$ 。
题解
题目解析
我做这道题的时候用了一维数组, 结果我没想到 $i,j$ 状态可以由 $i-1,k\quad(k\in F)$ 的任意状态转移…
所以需要开一个二维滚动数组, 这样的话就可以从上一状态的任意位置转移了. 它的转移方程可以这么表示:
解释一下, 就是第 $i$ 状态的 $j$ 可以由 $i-1$ 状态不选这个的种类数和 $i-1$ 的状态已经拥有$j-a[i]\%F+F$ 的种类数求和即可.
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define MOD(size) const long long MOD = size
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define T_ int T;cin >> T;while(T--)
typedef pair<int,int> PII;
typedef long long ll;
typedef long double lb;
typedef unsigned long long ull;
MAXN(2000);
MOD(1e8);
int a[MAXN],dp[2][MAXN];
signed main(){
CIN_;CIN;
int n,f;
cin >> n >> f;
fa(i,1,n) cin >> a[i];
dp[0][0] = 1;
fa(i,1,n){
int p = i % 2;
fa(j,0,f-1){
dp[p][j] = (dp[(p+1)%2][j] + dp[(p+1)%2][(j-(a[i]%f)+f)%f])%MOD;
}
}
cout << dp[n%2][0] - 1 << endl;
return 0;
}
|
[USACO3.1] 邮票 Stamps
题目描述
给一组 $n$ 枚邮票的面值集合和一个上限 $k$ —— 表示信封上能够贴 $k$ 张邮票。请求出最大的正整数 $m$，满足 $1$ 到 $m$ 的面值都可以用不超过 $k$ 张邮票表示出来。
输入格式
输入的第一行是两个整数，分别代表邮票上限 $k$ 和邮票面值数 $n$。
自第二行起，除最后一行外，每行有 $15$ 个整数 $a_i$ ，最后一行的整数个数不超过 $15$，共有 $n$ 个整数，第 $i$ 个整数代表第 $i$ 种邮票的面值 $a_i$。
输出格式
输出一行一个整数代表 $m$。若 $m$ 不存在请输出 $0$。
样例 #1
样例输入 #1
样例输出 #1
提示
样例输入输出 1 解释
有 $1$ 分和 $3$ 分的邮票；你最多可以贴 $5$ 张邮票。很容易贴出 $1$ 到 $5$ 分的邮资（用 $1$ 分邮票贴就行了），接下来的邮资也不难：
- $6 = 3 + 3$。
- $7 = 3 + 3 + 1$。
- $8 = 3 + 3 + 1 + 1 $。
- $9 = 3 + 3 + 3 $。
- $10 = 3 + 3 + 3 + 1 $。
- $11 = 3 + 3 + 3 + 1 + 1 $。
- $12 = 3 + 3 + 3 + 3 $。
- $13 = 3 + 3 + 3 + 3 + 1$。
然而，使用 $5$ 枚 $1$ 分或者 $3$ 分的邮票根本不可能贴出 $14$ 分的邮资。因此，答案为 $13$。
数据规模与约定
对于 $100\%$ 的数据，保证 $1 \leq k \leq 200$，$1 \leq n \leq 50$，$1 \leq a_i \leq 10^4$。
说明
题目翻译来自 NOCOW。
题解
题目解析
很奇怪熬! 明明这道题考虑最少组成价值的邮票的数量就好了啊…
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define MOD(size) const long long MOD = size
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define T_ int T;cin >> T;while(T--)
typedef pair<int,int> PII;
typedef long long ll;
typedef long double lb;
typedef unsigned long long ull;
MAXN(1e7);
int a[MAXN],b[MAXN],dp[MAXN];
signed main(){
CIN_;CIN;
int k,n;
cin >> k >> n;
fa(i,1,n) cin >> a[i];
mem(dp,0x3f);
dp[0] = 0;
fa(i,1,n){
fa(j,a[i],2000000){
dp[j] = min(dp[j],dp[j-a[i]]+1);
}
}
fa(i,1,2000000){
if(dp[i] > k){
cout << i - 1 << endl;
break;
}
}
return 0;
}
|
