AtCoder Beginner Contest 145

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\)，这些列要消去所需的最小代价
转移：

\[f_{i,j}=\min_{p=i+1}^n f_{p,j-1}+\max (0,a_p-a_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);
    for (int i = 1; i <= n; i++)    f[i][1] = a[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= n - k; j++) {
            for (int p = i + 1; p <= n; p++) {
                f[p][j] = min (f[p][j], f[i][j-1] + max (0, a[p] - a[i]));
            }
        }
    }
    for (int i = 1; i <= n; i++)    ans = min (ans, f[i][n-k]);
    cout << ans;
}

//很多边界细节
//对于ai,如果ai<=a[i-1],则消掉前面的时候会顺便把他消掉,若大于，可以选择直接删除
//问题转化为n中选n-k个(不变)留下的最小代价