AtCoder Beginner Contest 145
https://atcoder.jp/contests/abc145
D - Knight
乍一看以为是dp，但是数据范围不允许。
仔细一看发现，两种操作的次数是固定的，可以枚举出来每种操作分别进行了多少次，如 \((1,2)\) 走了 \(a\) 次，总共走了 \(b\) 次，那么方案就是 \(\C_{b}^{a}\)，组合数学小题。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, m;
ll ans, fact[N], infact[N];
int qmi(int a, int k, int p){
int res = 1;
while(k){
if(k & 1)
res = (ll)res * a % p;
a = (ll)a * a % p;
k >>= 1;
}
return res;
}
ll C(int a, int b) {
return (ll)fact[a] * infact[b] % mod * infact[a - b] % mod;
}
int main () {
fact[0] = infact[0] = 1;
for(int i = 1; i < N; i++){
fact[i] = (ll)fact[i-1] * i % mod;
infact[i] = (ll)infact[i-1] * qmi(i, mod - 2,mod) % mod;
}
cin >> n >> m;
//枚举(1,2)
for (int i = 0; i <= n; i++) {
int dx = n - i, dy = m - 2 * i; //还剩dx,dy
if (dx < 0 || dy < 0) continue;
//剩下都走(2,1),走dy次
if (dy * 2 != dx) continue;
// cout << i << ' ' << dy << endl;
(ans += C (i + dy, i)) %= mod;
}
cout << ans << endl;
}
//枚举一种走多少次,看看剩下能走多少
E - All-you-can-eat
一开始记忆化搜索疯狂RE，原因是递归次数过多导致爆栈。
其实这题非常明显：每个物品只有选和不选————那不就是典型的01背包吗。
先排个序，体积小的在前面一定更优：
喜多私密马森hhh
然后直接背包就可以了，注意体积转移那里的边界：\(a_i+t-1\)，因为题目说最后一个任务只要在ddl之前开始了就会一直执行下去
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int, int> pii;
const int N = 3005;
int n, t, f[N*2]; //f[j]: 考虑到第i个,耗时j
int ans;
pii p[N];
int main () {
cin >> n >> t;
for (int i = 1; i <= n; i++) cin >> p[i].first >> p[i].second;
sort (p + 1, p + n + 1);
for (int i = 1; i <= n; i++) {
for (int j = p[i].first + t - 1; j >= p[i].first; j--) {
f[j] = max (f[j], f[j-p[i].first] + p[i].second);
}
}
for (int i = 0; i < 6000; i++) ans = max (ans, f[i]);
cout << ans << endl;
}
//01背包
F - Laminate
线性dp。
这个状态设计很神奇。
首先是问题转化：对于 \(a_i\),如果 \(a_i\leq a_{i-1}\),则消掉前面的时候会顺便把他消掉。若大于，可以选择直接删除
考虑怎么删除最优，则等价于留下的 \(n-k\) 个数消掉的代价最小
\(dp\) 状态设计：\(f_{i,j}:\) 选了 \(j\) 列，最左边那一列为 \(i\)，这些列要消去所需的最小代价
转移：
注意初始化！！！
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 305;
int n, k, a[N];
ll f[N][N]; //f[i][j]: 选了j列,最左边那一列为i 的最小代价
ll ans = 1e18;
int main () {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n == k) {cout << 0; return 0;} //全部删掉
memset (f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n - k; j++) {
for (int t = 0; t < i; t++) {
f[i][j] = min (f[i][j], f[t][j-1] + max (0, a[i] - a[t]));
}
}
ans = min (ans, f[i][n-k]);
}
cout << ans;
}
//很多边界细节
//对于ai,如果ai<=a[i-1],则消掉前面的时候会顺便把他消掉,若大于，可以选择直接删除
//问题转化为n中选n-k个(不变)留下的最小代价