代完善

背包DP的建模和应用

飞扬的小鸟

题意

$\space\space\space\space\space$一款众所周知的游戏的介绍

源码

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e4 + 10, M = 1010, INF = 1e9;

int up[N], down[N];//跳  降落
int d[N], q[N];//管道下上高度
int f[N][M];//枚举到第i个点且高度为j的时候跳的最小值
int n, m, k, p, l, h;
void mem()
{
    memset(f, 0x3f, sizeof f);
    for(int i = 1; i <= m; i ++) f[0][i] = 0;
}

void solve()
{
    for(int i = 1; i <= n; i ++)//枚举到第i个点
    {
        //枚举第i个点的高度
        for(int j = 1; j <= m; j ++) // 不能枚举管子的高度来进行枚举 因为此处是完全背包 我们不知道选了几次 枚举实际可行高度无法叠加选举次数
        {
            if(j >= up[i - 1])//如果此处高于大于上一次转移的高度
            {
                f[i][j] = min(f[i][j], f[i - 1][j - up[i - 1]] + 1);//从i - 1处点击过来
                f[i][j] = min(f[i][j], f[i][j - up[i - 1]] + 1);  //从本次这个地方连续点击转移过来 判断多次点击
            }
            if(j == m)//到了顶点
            {
                for(int k = m - up[i - 1]; k <= m; k ++)//到了顶点可能是由 m - up[i - 1]的最低处到m个所有范围的最值 因为都可以到m
                {
                    f[i][j] = min(f[i][j], f[i - 1][k] + 1);
                    f[i][j] = min(f[i][j], f[i][k] + 1);
                }
            }

            // if(j >= d[i] + 1 && j <= q[i] - 1 && j + down[i - 1] <= m)
            //     f[i][j] = min(f[i][j], f[i - 1][j + down[i - 1]]);

        }    
        //下降和上升是独立操作 不可合并一个循环调用 因为我们的上升是可以多次点击 要与下降区分对待
         //枚举降的情况
        for(int j = d[i] + 1; j <= q[i] - 1; j ++)
            if(j + down[i - 1] <= m)   f[i][j] = min(f[i][j], f[i - 1][j + down[i - 1]]);

        //不符合的地方置为INF (非法解)
        for(int j = 1; j <= d[i]; j ++) f[i][j] = INF;
        for(int j = q[i]; j <= m; j ++) f[i][j] = INF;        
    }

}

int main()
{
    cin >> n >> m >> k;
    for(int i = 0; i < n; i ++) cin >> up[i] >> down[i];

    for(int i = 1; i <= n; i ++) d[i] = 0, q[i] = m + 1; //初始化 问题主要解决题意不是顺序输入即可
    for(int i = 1; i <= k; i ++) 
    {
        cin >> p >> l >> h;
        d[p] = l, q[p] = h;
    }

    mem();
    solve();

    int cnt = k, ans = INF;
    for(int i = n; i >= 1; i --)
    {
        for(int j = d[i] + 1; j <= q[i] - 1; j ++)  ans = min(ans, f[i][j]);

        if(ans != INF) break;
        if(q[i] <= m) cnt --;  //代表这个有水管
    }

    if(cnt == k) cout << 1 << endl << ans << endl; // 全部的管道通过
    else cout << 0 <<endl << cnt << endl;
}

线性DP篇章

P2501 [HAOI2006]数字序列

解析—待完善

$$ f[i] = min(f[pre[i]] + \sum_{j = pre[i] + 1}^{k} | b[j] - b[pre[i]] | + \sum_{j = k + 1}^{i - 1} |b[j] - b[i] | ) $$

源码

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
#define endl '\n'
const int N = 2e5 + 10, INF = 1e9 + 7;

LL n, len, b[N]; // 二分优化查询
LL q[N], f[N];  //长度为i的最长不下降子序列的最小结尾 f[i]以i结尾的最长不下降子序列长度
LL g[N], pre[N], suf[N]; // g[i] 最后一位是b[i]时单调不降的代价 前缀 后缀
vector<int> last[N]; //记录长度为i的最长不降子序列的结尾

int main()
{

    cin >> n;
    for(int i = 1; i <= n; i ++) 
    {
        int x;
        cin >> x;
        b[i] = x - i;
    }

    b[0] = - INF, b[n + 1] = INF;

    for(int i = 1; i <= n + 1; i ++)
    {
        LL l = 0, r = len;
        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            if(q[mid] <= b[i]) l = mid;
            else r = mid - 1;
        }

        len = max(len, r + 1);
        q[r + 1] = b[i];

        f[i] = r + 1;
        last[f[i]].push_back(i); 
    }

    last[0].push_back(0);
    memset(g, 0x3f, sizeof g);
    g[0] = 0;

    for(int i = 1; i <= n + 1; i ++)
    {
        int Size = last[f[i] - 1].size();
        for(int j = 0; j < Size; j ++) //枚举每个转移过来的last[i]
        {
            int from = last[f[i] - 1][j];

            if(from > i || b[from] > b[i]) continue;
            pre[from] = suf[i] = 0;
            //计算i -> k 的前缀    
            for(int k = from + 1; k <= i - 1; k ++)
                pre[k] = pre[k - 1] + abs(b[k] - b[from]);
            //计算 k + 1 -> j 的后缀    
            for(int k = i - 1; k >= from + 1; k --)
                suf[k] = suf[k + 1] + abs(b[k] - b[i]);

            for(int k = from; k <= i - 1; k ++)
               g[i] = min(g[i], g[from] + pre[k] + suf[k + 1]);

        }
    }

    cout << len <<endl<< g[n + 1] << endl;//因为n的时候 可能需要进行修改 所以输出n + 1

}

P1156 垃圾陷阱

//建模  垃圾的高度-> 体积 存活的时间 -> 价值 即求体积被塞满或者塞爆时候的最小价值

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
using namespace std;

#define endl '\n'
const int N = 3e3 + 10, INF = 1e9 + 7;

int h, n;

string s;
struct Node
{
    int t, v, h;
}q[N];

bool cmp(Node a, Node b)
{
    return a.t < b.t;
}
int f[N][N]; // 枚举到第i个垃圾 且高度为j的时候的最大存活时间

int main()
{
    cin >> h >> n;

    for(int i = 1; i <= n; i ++) cin >> q[i].t >> q[i].v >> q[i].h;

    sort(q + 1, q + n + 1, cmp);

    memset(f, -0x3f, sizeof f);
    f[0][0] = 10;
    int res = 10;
    for(int i = 1; i <= n; i ++)
    {

        for(int j = 0; j <= h; j ++)
       {   

            if(f[i - 1][j] < q[i].t - q[i - 1].t) continue;

            if(j + q[i].h >= h)
            {
                cout << q[i].t << endl;
                return 0;
            }


            f[i][j + q[i].h] = max(f[i - 1][j] - (q[i].t - q[i - 1].t), f[i][j + q[i].h]);
            f[i][j] = max(f[i][j], f[i - 1][j] + q[i].v - (q[i].t - q[i - 1].t));

       }
        res = max(res, f[i][0] + q[i].t);  
    }


    cout <<res << endl;


}

滚动数组优化

for(int i = 1; i <= n; i ++)
    {

        int cur = i & 1, pre = cur ^ 1;
        memset(f[cur], -0x3f, sizeof f[cur]);
        for(int j = h; j >= 0; j --)
       {   
            if(f[pre][j] < q[i].t - q[i - 1].t) continue;
            if(j + q[i].h >= h)
            {
                cout << q[i].t << endl;
                return 0;
            }
            f[cur][j + q[i].h] = max(f[pre][j] - (q[i].t - q[i - 1].t), f[cur][j + q[i].h]);
            f[cur][j] = max(f[cur][j], f[pre][j] + q[i].v - (q[i].t - q[i - 1].t));
       }
        res = max(res, f[cur][0] + q[i].t);  
    }