NOIP2014 Day1 T3(背包DP)

发表于 | 分类于 | | + s

题目是一个无限背包+01背包，但是要先做无限背包，再做01背包。如果先做01背包，那么在做无限背包的时候会出现多次下降的情况。
根据题目，很容易想出设$f[i][j]$为在$x=i, h=j$时的最小点击次数，那么有下列方程(无限背包部分, 即上升部分)
$$f[i][j] = min(f[i][j], f[i-1][j-kx]+1)$$
很明显，这样的做法TLE。
我们回想无限背包的式子，$f[v] = max(f[v], f[v-w[i]]+c[i])$对吧？应该大部分人都记得这个“滚动后的式子”，而原式都不记得了，原式为设$f[i][v]$为前$i$个物品装进$v$容量的最大利益。则状态转移方程为
$$f[i][v] = max(f[i-1][v], f[i][v-w[i]]+c[i])$$
这个方程是”继承$f[i-1]$的值“或者”在$f[i]$中已经计算过的值再用来转移(即实现了多重)”，我们的原方程是不是也可以这样呢？答案是肯定的。
原方程可化为
$$f[i][j] = min(f[i][j-x]+1, f[i][j-x]+1)$$
这样就不会超时了，处理之后的01背包，直接在多重处理完后扫一遍，$f[i][j] = min(f[i][j], f[i-1][j+y])$就能算出来了。
注意此题要因为上升高度大于$m$则为$m$，需要进行特殊判定，并且每个是管道的状态也要转移，因为这个对多重做出了贡献，在处理完之后再进行覆盖最大值即可，否则这里会丢掉25分。直接沦为暴力选手

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;

const int MAXN = 10000 + 5, MAXM = 1000 + 5, INF = 1000000000;

int n, m, k, f[MAXN][MAXM], d[MAXN], u[MAXN], l[MAXN], h[MAXN];

void clean() {
    for (int i=0;i<=n;i++) {
        l[i] = -1;
        h[i] = m + 1;
        f[i][0] = INF + 1;
        for (int j=1;j<=m;j++) {
            if (i==0) f[i][j] = 0; else f[i][j] = INF;
        }
    }
}
void init() {
    clean();
    for (int i=1;i<=n;i++) {
        scanf("%d%d", &u[i], &d[i]);
    }
    for (int i=1;i<=k;i++) {
        int p, x, y;
        scanf("%d%d%d", &p, &x, &y);
        l[p] = x, h[p] = y;
    }
}
void solve() {
    int zz = 0, ans = INF;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            if (j-u[i]>0) {
                f[i][j] = min(f[i][j], f[i][j-u[i]]+1);
                f[i][j] = min(f[i][j], f[i-1][j-u[i]]+1);
            }
            if (j==m) {
                for (int o=0;o<u[i];o++) {
                    f[i][j] = min(f[i][j], f[i][m-o]+1);
                    f[i][j] = min(f[i][j], f[i-1][m-o]+1);
                }
            }
        }
        for (int j=1;j<=m;j++) {
            if (j+d[i]<=m) f[i][j] = min(f[i][j], f[i-1][j+d[i]]);
        }
        for (int j=1;j<=l[i];j++) f[i][j] = INF;
        for (int j=h[i];j<=m;j++) f[i][j] = INF;
    }
    for (int i=1;i<=n;i++) {
        int ap = INF, flag = 0;
        for (int j=1;j<=m;j++) {
            if (f[i][j]<INF) flag = 1;
            ap = min(ap, f[i][j]);
        }
        if (!flag) {printf("0\n%d\n", zz); return ;} else ans = ap;
        if (l[i]!=-1) zz++;
    }
    printf("1\n%d\n", ans);
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d%d%d", &n ,&m, &k)==3) init(), solve();
    return 0;
}

2018.10.2，注意检查 DP 转移的完全性

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

using namespace std;

namespace flyinthesky {  

    const int MAXN = 10000 + 5, MAXM = 1000 + 5, INF = 1000000000;

    struct data {int l, h;} pp[MAXN];

    int n, m, k, dp[MAXN][MAXM], x[MAXN], y[MAXN], vis[MAXN][MAXN];

    void clean() {
        for (int i = 0; i <= n; i++) 
        for (int j = 0; j <= m; j++) dp[i][j] = INF, vis[i][j] = 0;
        for (int i = 0; i <= n; i++) pp[i] = (data){0, m + 1};
    }
    int solve() {
        scanf("%d%d%d", &n, &m, &k);
        clean();
        for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]);
        for (int pos, i = 1; i <= k; i++) {
            scanf("%d", &pos);
            scanf("%d%d", &pp[pos].l, &pp[pos].h);
            for (int j = 0; j <= pp[pos].l; j++) vis[pos][j] = 1;
            for (int j = pp[pos].h; j <= m; j++) vis[pos][j] = 1;
        }
        for (int i = 1; i <= m; i++) dp[0][i] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = x[i - 1]; j <= m; j++) {
                dp[i][j] = min(dp[i][j], dp[i][j - x[i - 1]] + 1);
                if (!vis[i - 1][j - x[i - 1]]) dp[i][j] = min(dp[i][j], dp[i - 1][j - x[i - 1]] + 1);
            //    printf("i=%d, j=%d, dp=%d\n", i, j, dp[i][j]);
            }
            for (int j = m; j >= max(m - x[i - 1], 1); j--) {
                dp[i][m] = min(dp[i][m], dp[i][j] + 1);//不要忘了
                if (!vis[i - 1][j]) dp[i][m] = min(dp[i][m], dp[i - 1][j] + 1);
            }
            for (int j = 1; j + y[i - 1] <= m; j++) if (!vis[i - 1][j + y[i - 1]]) dp[i][j] = min(dp[i][j], dp[i - 1][j + y[i - 1]]);
        }
        /*for (int j = m; j >= 0; j--)
        for (int i = 0; i <= n; i++) printf("%d%c", vis[i][j], i == n ? '\n' : ' ');
        puts("");
        for (int j = m; j >= 0; j--)
        for (int i = 0; i <= n; i++) printf("%c%c", dp[i][j] == INF ? 'u' : dp[i][j] + '0', i == n ? '\n' : ' ');*/
        int tot = 0;
        for (int i = 1; i <= n; i++) {
            int st = pp[i].l + 1, ed = pp[i].h - 1;
            if (!(st == 1 && ed == m)) ++tot;
            int fl = 0;
            for (int j = st; j <= ed; j++) if (dp[i][j] != INF) {fl = 1; break;}
            if (fl) continue;
            return printf("0\n%d\n", tot - 1);
        }
        int ans = INF;
        for (int j = 1; j <= m; j++) ans = min(ans, dp[n][j]);
        printf("1\n%d\n", ans);
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------