Codeforces Round #538 (Div. 2) 解题报告

A Got Any Grapes?

顺序判断即

比赛的时候忘记写 else 既然 PP 了,然后就 FST

#include <cstdio>
int an,dm,mi;
int gr,pu,bl;
int main(){
    scanf("%d%d%d", &an, &dm, &mi);
    scanf("%d%d%d", &gr, &pu, &bl);
    if(an > gr) {
        printf("NO\n");
        return 0;
    }
    else gr -= an;
    if(pu + gr < dm){
        printf("NO\n");
        return 0;
    }
    else {
        if(pu <= dm) {dm -= pu; pu = 0;}
        else {pu -= dm; dm = 0;}
        if(gr < dm) {
            printf("NO\n");
            return 0;
        }
        else gr -= dm;
    }
    if(gr + pu + bl < mi) printf("NO\n");
    else printf("YES\n");
}

B Yet Another Array Partitioning Task

反正最后还是要前$ m \times k $ 个数字

直接离散化,然后见当前区间有$ m $ 个就收

#include <cstdio>
#include <algorithm>
const long long N = 2e5 + 1e4;
struct node{
    long long now, id;
}b[N];
long long n, m, k, cnt, time;
long long a[N];
bool vis[N];
bool cmp(node a, node b){
    return a.now > b.now;
}
int main(){
    scanf("%lld%lld%lld", &n, &m, &k);
    for(long long i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
        b[i].now = a[i], b[i].id = i;
    }
    std::sort(b + 1, b + n + 1, cmp);
    long long tmp = m * k;
    for(long long i = 1; i <= tmp; i++) vis[ b[i].id ] = true, cnt += b[i].now;
    printf("%lld\n",cnt);
    cnt = 0;
    for(long long i = 1; i <= n; i++){
        cnt += vis[i];
        if(cnt == m){
            time++;
            time < k && printf("%lld ",i);
            cnt = 0;
        }
    }
}

C. Trailing Loves (or L’oeufs?)

求 $ b $ 进制下 $ n! $ 的末尾的 0 的个数

显然我们要求中间乘出来有多少个$b$

接下来就是分解质因数,然后枚举求最小值即可

#include <cstdio>
#include <cmath>
const long long INF = 1e18 + 1e17;
inline long long Min(long long a, long long b){return a < b? a: b;}
struct node{
    long long now, cnt;
}pri[(int)(1e6)];
int pcnt;
long long n, b, tmp, cnt, ans = INF;
inline void get_pri(long long b){
    tmp = std::sqrt(b);
    for(long long i = 2; i <= tmp; i++){
        if(b % i == 0){
            pri[ ++pcnt ] = (node){i, 0};
            while(b % i == 0){
                pri[pcnt].cnt++;
                b/=i;
            }
        }
    }
    if(b != 1) pri[ ++pcnt ] = (node){b, 1};
}
int main(){
    scanf("%lld%lld", &n, &b);
    get_pri(b);
    for(int i = 1; i <= pcnt; i++){
        tmp = 1; cnt = 0;
        while(tmp * pri[i].now <= n){
            tmp *= pri[i].now;
            if(tmp < 0 || tmp % pri[i].now != 0) break;
            cnt += n / tmp;
        }
        ans = Min(ans, cnt/pri[i].cnt);
    }
    printf("%lld\n", ans);
}

D. Flood Fil

有一个非常显然的地方,就是我们每次有两个状态,当前联通部分向左对其或者想右对其

然后我们先把数列中的联通部分预处理出来,然后区间 dp 即可

#include <cstdio>
#include <cstring>
inline int Min(int a, int b){return a < b? a: b;}
const int N = 5100;
int n;
int a[N], l[N], r[N], f[N][N];
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    l[1] = 1;
    for(int i = 2; i <= n; i++){
        if(a[i] == a[i - 1]) l[i] = l[i - 1];
        else l[i] = i;
    }
    r[n] = n;
    for(int i = n - 1; i >= 1; i--){
        if(a[i] == a[i + 1]) r[i] = r[i + 1];
        else r[i] = i;
    }
    memset(f, 0x3f, sizeof(f));
    for(int i = 1; i<= n;i ++) f[ l[i] ][ r[i] ] = 0;
    for(int len = 0; len < n; len++){
        for(int i = 1,j; i + len <= n; i++){
            j = i + len;
            if(i > 1 && j < n && a[i - 1] == a[j + 1])
                f[ l[i - 1] ][ r[j + 1] ] = Min(f[ l[i - 1] ][ r[j + 1] ],f[i][j] + 1);
            if(i > 1)
                f[ l[i - 1] ][j] = Min(f[ l[i - 1] ][j], f[i][j] + 1);
            if(j < n)
                f[i][ r[j + 1] ] = Min(f[i][ r[j + 1] ], f[i][j] + 1);
        }
    }
    printf("%d", f[1][n]);
}

E. Arithmetic Progression

交互题目,60次询问内知道当前乱序等差数列的首项和公差

先二分找最大的,然后random_shuffle随机化询问,求与最大项差的 gcd 即为公差

#include <cstdio>
#include <algorithm>
int gcd(int a, int b){return b? gcd(b ,a%b): a;}
inline int Min(int a, int b){return a < b? a: b;}
inline int Aabs(int a){return a < 0? (0 - a): a;}
const int N = 1e6 + 1e5;
int n, global_tmp, d, max, chance_cnt = 60;
int a[N];
inline bool has_num(int now){
    printf("> %d\n",now);
    fflush(stdout);
    scanf("%d", &global_tmp);
    chance_cnt--;
    return global_tmp;
}
inline int binary_search_max(int max_limit){
    int left = 0, rig = max_limit, mid, res;
    while(left <= rig){
        mid = (left + rig) >> 1;
        if( has_num(mid) ) left = mid + 1;
        else rig = mid - 1, res = mid;
    }
    return res;
}
int main(){
    scanf("%d", &n);
    max = binary_search_max(1e9);
    for(int i = 1; i <= n; i++) a[i] = i;
    for(int i = 1; i <= 5; i++) std::random_shuffle(a + 1, a + n + 1);
    for(int i = 1; i <= Min(n ,chance_cnt); i++){
        printf("? %d\n", a[i]);
        fflush(stdout);
        scanf("%d", &global_tmp);
        if(global_tmp == max) continue;
        if(d == 0) d = Aabs(max-global_tmp);
        d = gcd(d , Aabs(max-global_tmp));
    }
    fflush(stdout);
    printf("! %d %d\n", max - (n - 1) * d, d);
}

F. Please, another Queries on Array?

这个题目首先得知道$\varphi(n)$的求法

然后就是乘积线段树和或线段树维护一下

就没有然后了

#include <cstdio>
const int N = 4e5 + 1e4;
const long long mod = 1e9 + 7;
int n, q, x, y, z, pcnt;
int a[N];
long long p[310], pri[N], inv[310];
char op[10];
inline long long ksm(long long a, long long p){
    long long res = 1;
    while(p){
        if(p & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        p >>= 1;
    }
    return res;
}
inline void prime(){
    for(int i = 2; i <= 300; i++){
        for(int j = 1; j <= pcnt; j++)
            if(i % p[j] == 0) pri[i] |= pri[ p[j] ];
        if(pri[i] == 0) {p[++pcnt] = i; pri[i] = (1LL << (pcnt - 1LL));}
    }
}
inline void get_inv(){
    for(int i = 1; i <= pcnt; i++)
        inv[i] = ksm(p[i], mod - 2);
}
// Segment Tree Start
struct node{
    long long val,pri;
    void operator+= (const node &b){
        this -> val = (this -> val * b.val) % mod;
        pri |= b.pri;
    }
}tree[N << 2], lazy[N << 2];
inline void pushup(int now){
    tree[now].val = (tree[now << 1].val * tree[now << 1 | 1].val) % mod;
    tree[now].pri = tree[now << 1].pri | tree[now << 1 | 1].pri;
}
inline void pushdown(int now, int lson, int rson){
    if(lazy[now].pri != 0){
        tree[now << 1].val  =  (1LL * tree[now << 1].val * ksm(lazy[now].val, lson)) % mod;
        tree[now << 1 | 1].val  =  (1LL * tree[now << 1 | 1].val * ksm(lazy[now].val, rson)) % mod;
        tree[now << 1].pri |= lazy[now].pri;
        tree[now << 1 | 1].pri |= lazy[now].pri;
        lazy[now << 1].val = (1LL * lazy[now << 1].val * lazy[now].val) % mod;
        lazy[now << 1 | 1].val = (1LL * lazy[now << 1 | 1].val * lazy[now].val) % mod;
        lazy[now << 1].pri |= lazy[now].pri;
        lazy[now << 1 | 1].pri |= lazy[now].pri;
        lazy[now].val = 1LL; lazy[now].pri = 0;
    }
}
inline void query_mut(int now, int left, int rig, int from, int to, int val){
    if(from <= left && rig <= to){
        tree[now].val = (1LL * tree[now].val * ksm(val, (rig - left + 1LL))) % mod;
        tree[now].pri |= pri[val];
        lazy[now].val = (lazy[now].val * val) % mod;
        lazy[now].pri |= pri[val];
        return ;
    }
    int mid = (left + rig) >> 1;
    pushdown(now, mid - left + 1LL, rig - mid);
    if(from <= mid) query_mut(now << 1, left, mid, from, to, val);
    if(to > mid) query_mut(now << 1 | 1, mid + 1, rig, from, to, val);
    pushup(now);
}
inline node query_sum(int now, int left, int rig, int from, int to){
    if(from <= left && rig <= to) return tree[now];
    int mid = (left + rig) >> 1;
    node res = (node){1, 0};
    pushdown(now, mid - left + 1LL, rig - mid);
    if(from <= mid) res += query_sum(now << 1, left, mid, from, to);
    if(to > mid) res += query_sum(now << 1 | 1, mid + 1, rig, from, to);
    pushup(now);
    return res;
}
inline void build_tree(int now, int left, int rig){
    lazy[now].val = 1; lazy[now].pri = 0;
    if(left == rig){
        scanf("%lld", &tree[now].val);
        tree[now].pri = pri[ tree[now].val ];
        return ;
    }
    int mid = (left + rig) >> 1;
    build_tree(now << 1, left, mid);
    build_tree(now << 1 | 1, mid + 1, rig);
    pushup(now);
}
// Segment Tree End
int main(){
    prime();
    get_inv();
    scanf("%d%d", &n, &q);
    build_tree(1, 1, n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    while(q--){
        scanf("%s", op);
        if(op[0] == 'M'){
            scanf("%d%d%d", &x, &y, &z);
            query_mut(1, 1, n, x, y, z);
        }
        else {
            scanf("%d%d", &x, &y);
            node tmp = query_sum(1, 1, n, x, y);
            for(int i = 1; i <= pcnt; i++){
                if((tmp.pri >> (i - 1LL)) & 1LL)
                    tmp.val = (((tmp.val * (p[i] - 1) ) % mod) * inv[i]) % mod;
            }
            printf("%lld\n", tmp.val);
        }
    }
}


]]>

树形背包 — Luogu P1273 有线电视网

0x01 写在开头

题目链接:[https://www.luogu.org/problemnew/show/P1273]

前置技能 : 树形DP

如果做过选课的话,想必各位一看到就知道这是一道树形DP的题目

0x02 题目

题目中要求我们在以收入$\geq 0$的前提下,支持尽可能多的叶子节点

因此我们可以这么定义一个类似背包状态转移方程
$$
f(now,i+j)=max(f(now,i+j),f(son,j)+f(now,i)-val)
$$
这不就是背包吗<(=°д)ノ

边界条件
$$
f(i,j)=-INF(0\leq i \leq N,0 \leq j \leq M)
$$
设为$-INF$是为了防止无法转移

看起来很显然是吧

让我们来看看代码:

0x03 代码

#include <cstdio>
#include <cstring>
const int N=3100;
inline int Max(int a,int b){return a>b?a:b;}
int _case;
int ans,v,w,n,m,son[N];
int f[N][N];
// edge start
struct edge{
    int to,next,val;
}e[N];
int ehead[N],ecnt;
inline void add_edge(int now,int to,int val){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].val=val;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end
// dfs start
void dfs(int now){
    if(now>n-m){// 只有用户才会算到叶子节点中
        son[now]=1;
        return ;
    }
    f[now][0]=0;
    for(int u=ehead[now];u;u=e[u].next){
        dfs(e[u].to);
        for(int i=son[now];i>=0;i--){
            for(int j=1;j<=son[e[u].to];j++){// 注意循环顺序,不这么循环会重复计算一些东西
                f[now][i+j]=Max(f[now][i+j],f[now][i]+f[e[u].to][j]-e[u].val);
            }
        }
        son[now]+=son[e[u].to];
    }
}
// dfs end
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-m;i++){
        scanf("%d",&_case);
        while(_case--){
            scanf("%d%d",&v,&w);
            add_edge(i,v,w);
        }
    }
    memset(f,-0x3f,sizeof(f));
    for(int i=1;i<=m;i++) scanf("%d",&f[n-m+i][1]);
    dfs(1);
    for(int i=1;i<=m;i++){
        if(f[1][i]>=0) ans=i;
    }
    printf("%d",ans);
}
]]>

ZJOI 2007/Luogu P2272 — 最大半连通子图 — Tarjan缩点+Dfs

图论天坑

题目


题目链接: [https://www.luogu.org/problemnew/show/P2272]
题目索然看起来好像很清楚的样子,然而没人我知道中间的问号有什么用,直到我去网上查了一回 对于一张图G,它中间任意取上两个点u,v其中有一条uv 或者 vu 的边,我们就称这张图为半连通图 如果从一张图G选出任意几个点与这几个点有关的所有的边,形成一张图G',如果G'是一张半连通图,我们就称G'G半连通子图 而在图G所有的G'中节点数最多的图,为图G最大半连通子图 然后怎么做呢? 首先,我们可以很清楚的知道,一张图中可能有多个环,而这个环中任意一个点到外面一个点,可以形成一个半连通子图,我们根据每一个点来做太繁杂了 也就是说我们可以把环当做有权值一个点来判断,如果是自环权值为1就行了 怎么缩点(把环缩成点)相信大家心里都有数了,Tarjan判环,\(O(n+m)\)
关于 Tarjan 的做法,在这里不多做赘述,详情参照 uncle-lu 大佬的博客: [http://uncle-lu.org/archives/99]
但是 Tarjan 仅仅能够做到判断环,怎么缩点啊? 去当偶像吧建个新图啊! 怎么建呢?染色法: 通过将在同一环上的所有点标上一个编号(颜色),然后遍历所有点,把编号和编号相连接 至于后面的过程,我们首先可以知道,对于一个经过缩点后的图,它一定是一个森林,也就是说,我们只需要从入度为0的点开始查找就可以了 是不是有点懵?看一下代码把:

代码


#include <cstdio>
#include <cstring>
using namespace std;
// edge start
struct edge{
    int to,next;
}e[1100000],ne[1100000];
int ehead[110000],ecnt,necnt,nehead[1100000];
inline void add_edge(edge e[],int &ecnt,int ehead[],int from,int to){// add_edge 加边 因为要建两个图就传进来一些别的参数
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].next=ehead[from];
    ehead[from]=ecnt;
}
// edge end;
int n,m,mod,u,v,ans,acnt;
// n,m,mod,u,v 读入用,参照题意
// ans 最大点数 acnt 重复次数
// tarjan start
int DFN[110000],LOW[110000],huan[110000],time;// DFN[] LOW[] Tarjan 用 time 时间戳 huan[]记录权值
int s[1100000],scnt;// 堆栈
int col[110000],colcnt;// 记录每个点对应的颜色
bool vis[110000];// 记录访问次数
inline void tarjan(int now){// tarjan 标准 Tarjan
    DFN[now]=LOW[now]=++time;
    s[++scnt]=now;
    vis[now]=true;
    for(int i=ehead[now];i;i=e[i].next){
        if(!DFN[e[i].to]){
            tarjan(e[i].to);
            LOW[now]=LOW[now]<LOW[e[i].to]?LOW[now]:LOW[e[i].to];
        }
        else if(vis[e[i].to]){
            LOW[now]=LOW[now]<DFN[e[i].to]?LOW[now]:DFN[e[i].to];
        }
    }
    if(LOW[now]==DFN[now]){
        colcnt++;
        do{// 无论如何都要进行一遍,至少自己要加进去
            huan[colcnt]++;
            col[s[scnt]]=colcnt;
            vis[s[scnt]]=0;
            scnt--;
        }while(now!=s[scnt+1]);
    }
}
inline void tarjan_init(){// tarjan_iniit 标准 Tarjan
    for(int i=1;i<=n;i++) if(!DFN[i]) tarjan(i);
}
// tarjan end
bool cf(int from,int to){// cf 判断从from到to是不是已经有一条边
    for(int i=nehead[from];i;i=ne[i].next){// 遍历
        if(ne[i].to==to) return false;// 有返回否
    }
    return true;// 无返回是
}
inline void new_graph_build(){// new_graph_build建立新图
    for(int u=1;u<=n;u++){// 遍历点
        for(int i=ehead[u];i;i=e[i].next){// 遍历边
            if(col[u]==col[e[i].to]) continue;// 颜色相同为什么还要再加呢?
            if(cf(col[u],col[e[i].to])){// 判断有没有重复的边
                add_edge(ne,necnt,nehead,col[u],col[e[i].to]);// 加边
            }
            LOW[col[e[i].to]]++;// 判断入度,入度为0即为根
        }
    }
}
void find(int now){// 查找最大节点数
    vis[now]=true;// 不能重复查找一个边
    for(int i=nehead[now];i;i=ne[i].next){
        if(!vis[ne[i].to]) find(ne[i].to);// 没有找过再找
        DFN[now]=DFN[now]>DFN[ne[i].to]?DFN[now]:DFN[ne[i].to];// 去最大的情况
    }
    DFN[now]+=huan[now];// 别忘了自己还有权
}
void find_cnt(int now){
    vis[now]=true;// 不能重复查找
    for(int i=nehead[now];i;i=ne[i].next){
        if(!vis[ne[i].to]) find_cnt(ne[i].to);
        if(DFN[now]==huan[now]+DFN[ne[i].to]) col[now]=(col[now]+col[ne[i].to])%mod;// col[] 有多少个和当前节点当前最多节点相同的节点(多读几遍
    }
    if(!nehead[now]) col[now]=1;// 如果这个点没有边的话别忘记自环
    if(DFN[now]==ans) acnt=(acnt+col[now])%mod;// 如果是最大情况的话往答案上加wq
}
int main(){
// 读入
    scanf("%d%d%d",&n,&m,&mod);
    for(int i=1;i<=m;i++) {scanf("%d%d",&u,&v);add_edge(e,ecnt,ehead,u,v);}
    tarjan_init();// Tarjan
    memset(DFN,0,sizeof(DFN));// 没有用的数组可不能够浪费
    memset(LOW,0,sizeof(LOW));
    new_graph_build();
    memset(vis,false,sizeof(vis));
    memset(col,0,sizeof(col));
    for(int i=1;i<=colcnt;i++){
        if(LOW[i]==0){// 如果是根的话
            find(i);
            ans=ans>DFN[i]?ans:DFN[i];// 寻找最大答案
        }
    }
    memset(vis,false,sizeof(vis));
    //memset(DFN,0,sizeof(DFN));
    for(int i=1;i<=colcnt;i++){
        if(LOW[i]==0){// 从根找
            find_cnt(i);
        }
    }
    printf("%d\n%d",ans,acnt);// 输出
}

End


不管如何在这道题目里多少还是有点树型DP的影子的,不过图论题目要小心,错一个变量很难看出来的… ]]>

初学DP(5) – 棋盘型DP – NOIP 2000 提高组 第四题 方格取数 & POJ 2948 Martian Mining

棋盘型DP 棋盘型DP,是DP中比较坑的一种,大多数都可以用深搜AC拿上部分分,剩下的tle2333 所以这个就需要DP,通常我们是从左上朝右下找,当然了,棋盘DP却常常有种暴力的感觉

方格取数

题目链接: [http://codevs.cn/problem/1043/]
输入的方法很简单,也并没有什么复杂的预处理 对于这样一个棋盘,我们很容易想到他的阶段:从 f(i,j) 到 f(k,l) 的最优解 很明显这里已经不能用区间DP了,我们需要对 i j k l 进行枚举,另外,我们很容易发现,要是值最大,两条路径不应重合 针对与 f[i][j][k][l] 他是由两个坐标所组成的,所以我们就要分别考虑第一个坐标与第二个坐标的变化,每个坐标都有两种变化的可能,所以我们的状态转移方程应是:
f [ i ] [ j ] [ k ] [ q ] = max ( max ( f [ i – 1 ] [ j ] [ k – 1 ] [ q ] , f [ i ] [ j – 1 ] [ k ] [ q – 1 ] ) , max ( f [ i ] [ j – 1 ] [ k – 1 ] [ q ] , f [ i – 1 ] [ j ] [ k ] [ q – 1 ] ) ) +a [ k ] [ q ] + a [ i ] [ j ]
经过了这一步,我们就可以得到代码:

代码


#include <iostream>
#include <cstdio>
using namespace std;
int n,x,y,c;// 读入用
int a[20][20],f[20][20][20][20];//a[][] 存图 f[][] 动归
int main(){
// 读入
    scanf("%d",&n);
// 并不知道有多少组,那就无限输入吧
    while(1){
        scanf("%d%d%d",&x,&y,&c);
        if(x==0&&y==0&&c==0) break;// 全是 0 就该出来了
        a[x][y]=c;
    }
// 枚举
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                for(int q=1;q<=n;q++){
                    f[i][j][k][q]=max(max(f[i-1][j][k-1][q],f[i][j-1][k][q-1]),max(f[i][j-1][k-1][q],f[i-1][j][k][q-1]))+a[k][q]+a[i][j];//进行决策
                    if(i==k&&j==q) f[i][j][k][q]-=a[i][j];//如果两点相同,去掉重复的
                }
            }
        }
    }
// 输出
    printf("%d",f[n][n][n][n]);
}

Martian Mining

题目链接: [http://poj.org/problem?id=2948]

翻译


本人才疏学浅,无法做到完全翻译,所以我只会翻译题干,如果有不明确之处请指出 火星上有一个被分为n*m个格子的矿区,每格子中有两种矿石,在北边有一个厂子炼一种矿,西边也有一个厂子炼另一种矿,现在有两种传送带-自南向北与自东向西,并且一个格子上只能安一种,传送带还不能转弯. 如果矿石没有被送进它所属的厂子,就是废石,现在,问你最多能采多少矿

题目


第一眼过去dfs+记忆化搜索 可是确实可以通过这个推出来 我们在进行搜索时,从右下往左上搜。搜到最优解,然后保存下来,于是我们可以翻过来,从左上到右下然,找出每一段的最优解,然后相加,ok! 通过这个问题我们应当把每一种矿石的 i – j 的区域有多少存下来,让后我们可以得出 dp 方程
f [ i ] [ j ] = max ( f [ i – 1 ] [ j ] + yr [ i ] [ j ] , f [ i ] [ j – 1 ] + bl [ i ] [ j ] )
其中 f[][] 为动归用数组 yr[i][j] 与 bl[i][j] 都是一种矿石从第 i 个格子到第 j 个格子的对应矿石个数

End

]]>

初学DP(4) – 多重背包及其优化 – Codevs 3269

多重背包 我们曾经说过完全背包和01背包,但是这两个方法都有一个问题,就是物件个数都是一致的并且是确定的,但如果他不确定呢? 我们可以定义一个k循环来模拟他的件数,不过显然这样做的华时间复杂度会超过我们的想象 所以我们需要进行优化,优化的方式有两种

  • 二进制优化
  • 单调队列

二进制优化


我们来观察下面这几个数字 十进制 1 2 4 8 二进制 1 10 100 100 我们可以发现这几个数每次乘二,并且可以凑成从 1 到 1+2+4+8=15 的所有情况 至于是什么原因可以观察一下二进制数 1+10=11(3) 1-3凑齐 11+1=100(4) 1-3,4,5-7凑齐 没错每个为2^n的数,它的二进制中,第一位是1,后面全是0,这样一来我们只需要把是2^n次放并且和小于个数的数求出来,之后按个数相乘成为一个新的物品

单调队列


是否还记得队列呢? 单调队列也是队列,所谓的单调,就是指按队列中的顺序 是固定的,也就是指最优解永远放在最前面,但是问题来了,阶段不同的最优解改怎么办呢? 我们来推导一下
k=1
f[1] max( f[1]-1*w+1*w)
k=1
f[2] max(f[2]-2*w+2*w,f[1]-1*w+2*w)
k=1
f[3] max(f[3]-3*w+3*w,f[2]-2*w+3*w,f[1]-1*w+3*w)
于是我们发现
f[k]=f[k]-kw+kw f[n]=f[n]-nw+kw
所以我们可以对队列进行维护,所有存在队列里的值去掉 k*w 的部分

混合背包

题目链接: [http://codevs.cn/problem/3269/]
很裸的模板题了,我们直接开始写吧

二进制优化

时间: 4316 ms 内存: 1004 kb
#include <cstdio>
using namespace std;
int z,cnt,m;// 二进制拆分用
int n,V;// n 物品数量 V 体积
int v[10100000],w[10100000],alen;// v[] 体积 w[]价格 alen 长度
int f[10100000];// f[] 动归专用
int main(){
//读入
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&v[alen],&w[alen],&m);
  z=alen;// 将 z 保留住
        alen++;
        if(m==-1) m=V/v[z]; //如果为无限的话,就按能放下的最大值走
        cnt=m-1;//-1是因为已经有 1 了
       //开始拆分
  for(int j=2;;j*=2){
            if(cnt>j){//如果还能拆,继续插并增加物品件数
                cnt-=j;
                v[alen]=v[z]*j;
                w[alen]=w[z]*j;
                alen++;
            }
            else {
                v[alen]=v[z]*cnt;
                w[alen]=w[z]*cnt;
                alen++;
                break;
            }
        }
    }
// dp[] 二进制拆分玩就是一个 01 背包了
    for(int i=0;i<alen;i++){
        for(int j=V;j>=v[i];j--){
            if(f[ j-v[i] ]+w[i]>f[j]){
                f[j]=f[ j-v[i] ]+w[i];
            }
        }
    }
    printf("%d",f[V]);
}

单调队列

时间: 2430 ms 内存: 2 MB
#include <cstdio>
#include <iostream>
using namespace std;
int n,V,v,w,m;
int f[210000];// dp[]
struct node {
    int f,id;
}q[210000];
int l,r;
int main(){
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&v,&w,&m);
        if(m==-1||m*v>V) m=V/v;
        for(int j=0;j<v;j++){
            l=r=0;
            for(int k=j,id=0;k<=V;k+=v,id++){
                while(l!=r&&q[r-1].f<=f[k]-id*w) r--;// 如果队尾解不如当前解就去掉
                q[r++]=node{f[k]-id*w,id};
                while(l!=r&&id-q[l].id>m) l++;// 如果目前所有的所有数量也达不到队首要求也去掉
                f[k]=q[l].f+id*w;
            }
        }
    }
    printf("%d",f[V]);
}

极限优化


时间: 1952 ms 内存: 2 Mb
#include <cstdio>
#include <iostream>
using namespace std;
int n,V,v,w,m;
int f[210000];
struct node {
    int f,id;
}q[210000];
int l,r;
// 01背包
void oz(int v,int w){
    for(int i=V;i>=v;i--){
       f[i]=max(f[i],f[i-v]+w);
    }
}
// 完全背包
void wq(int v,int w){
    for(int i=v;i<=V;i++){
       f[i]=max(f[i],f[i-v]+w);
    }
}
// 单调队列优化多重背包
void queueyh(int v,int w,int m){
    for(int j=0;j<v;j++){
        l=r=0;
        for(int k=j,id=0;k<=V;k+=v,id++){
            while(l!=r&&q[r-1].f<=f[k]-id*w) r--;
            q[r++]=node{f[k]-id*w,id};
            while(l!=r&&id-q[l].id>m) l++;
            f[k]=q[l].f+id*w;
        }
    }
}
int main(){
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&v,&w,&m);
        if(m==-1||m*v>V) wq(v,w);// 如果m都放进来已经大于背包就可以直接用无限
        else if(m==1) oz(v,w);// 只有1个就交给01背包吧
        else queueyh(v,w,m);
    }
    printf("%d",f[V]);
}

END

多重背包实际上与前两中差别不大,不过重点在于优化,优化不得当直接TLE ]]>

初学DP(3.5) – 完全背包 – Luogu P1616 疯狂的采药

完全背包 我们先来回顾一下 01 背包

针对于有一定空间,一定数量的物品,每个物品只能放一个,我们可以把他当为 01 背包,它的状态转移方程是:
f[j]=max( f [ j – a [ i ] ] + a [ i ] , f [ j ] )
那么什么是完全背包呢? 针对于有一定空间,一定数量的物品,每个物品能放无数个的背包,我们称其为完全背包, 我们曾经在 初学DP (1) – 01 背包 – 装箱问题 & NOIP 2005 普及 第三题 采药 中提到过 01 背包的 j 循环 这层循环如果从小到大,你们他就会按个累加,那么也就是说把 j 循环从小到大,它,就变成了完全背包

疯狂的采药

这道题中他很明显的说了他和采药的不同点:
1.每种草药可以无限制地疯狂采摘。 2.药的种类眼花缭乱,采药时间好长好长啊!师傅等得菊花都谢了!
那tm不久是完全背包吗!!!!!! 所以你把采药的 j 循环倒一下,数组开大点,AC!!! ]]>

初学 DP(2) – 最长子序列 – NOIP 2004 提高 合唱队形 & NOIP 1999 提高 拦截导弹

最长严格上升子队列

题目链接: [ http://codevs.cn/problem/1576/ ]

题目

题目的意图已经很明显了,让我们在一个数组中找出一个最长的从小到大的子序列,想然我们可以对问题进行分化,我是怎么考虑的: 我们可以知道第一个数一定是一个长度子序列,那么在后面的数字只需要和他比较大小,比它晓得直接接在他的后面就行了,比如下面这三个数字
3 1 2
3 成为长度为 1 的一串,但后面两个都比它小 1 成为长度为 1 的一串,2 比它大,所以得到长度为 2 的子序列 所以我们可以得到下面的状态转移方程:
f [ i ] = f [ j ] + 1;

代码


#include <cstdio>
using namespace std;
int n;
int a[5100],f[5100];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    f[1]=1;
    for(int i=1;i<=n;i++){
        int max=0;
        for(int j=1;j<i;j++){
            if(f[j]+1>max&&a[i]>a[j]){
                max=f[j]+1;// 找出最大可能
            }
        }
        f[i]=max;// 赋值给 f[i]
    }
    printf("%d",f[n]+1);// 别往了自己也是一个单位长度
}

合唱队形

题目链接: [http://codevs.cn/problem/1058/]

题目


定睛一看,是不是有点眼熟,是的,它也是最长子序列 不过这道题是要求在中间找一个“峰值”,使其左边的最长升序子序列与右边最长降序子序列的长度加起来最大 其中就可以很容易得出这样一种思路 – 我们在动归的同时,把每个数左边与右边存下来,这样一来,问题的思路就明朗了

代码


#include <cstdio>
using namespace std;
int n;
struct node {
    int a,left,rig;
}a[110];
int main(){
    int max;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i].a);
    for(int i=1;i<=n;i++){
        max=0;
        for(int j=1;j<i;j++){
            if(a[j].a<a[i].a&&a[j].left+1>max){
                max=a[j].left+1;
            }
        }
        a[i].left=max;
    }
    for(int i=n;i>=1;i--){
        max=0;
        for(int j=n;j>i;j--){
            if(a[j].a<a[i].a&&a[j].rig+1>max){
                max=a[j].rig+1;
            }
        }
        a[i].rig=max;
    }
    max=0;
    for(int i=1;i<=n;i++){
        if(a[i].left+a[i].rig+1>max) max=a[i].left+a[i].rig+1;
    }
    printf("%d",n-max);
}

拦截导弹

题目链接: [http://codevs.cn/problem/1044/]
导弹拦截?拦截导弹?傻傻分不清楚 这道提的第一问就是一个简单的最长不降子序列,具体操作大家都明白 但是第二问求的是最少有几个最长不降子序列,这个就很艰难, 暴力当然会T,所以这题是有一个数学方法的,如果你想知道怎么求证,可以去bing 博主在这里只会讲讲这个定理
最少有几个不降子序列=最长上升序列的长度
以此类推,我们还可以得到:
最少有几个不升子序列=最长下降子序列的长度 最少有几个上升子序列=最长不升序列的长度 最少有几个不降子序列=最长不降序列的长度
那么这道题就很容易求解了,第一个输出最长不降子序列,第二个输出最长上升子序列

代码


#include <cstdio>
#include <cstring>
using namespace std;
int a[21],alen,max;
int f[21];
int main(){
    while(scanf("%d",&a[alen++])!=EOF);
    alen--;
    for(int i=0;i<alen;i++){
        for(int j=0;j<i;j++){
            if(a[j]>=a[i]&&f[j]+1>f[i]) f[i]=f[j]+1;
        }
    }
    for(int i=0;i<alen;i++) if(max<f[i]) max=f[i];
    printf("%d\n",max+1);
    memset(f,0,sizeof(f));
    for(int i=0;i<alen;i++){
        for(int j=0;j<i;j++){
            if(a[j]<a[i]&&f[j]+1>f[i]) f[i]=f[j]+1;
        }
    }
    max=0;
    for(int i=0;i<alen;i++) if(max<f[i]) max=f[i];
    printf("%d",max+1);
}

END

最长子序列有动归解是十分常见的解法,我们一般都会使用这种方法,当然如果你觉得不服,你也可以用贪心和暴力试试,说不定能A呢? ]]>

初学DP (1) – 01 背包 – 装箱问题 & NOIP 2005 普及 第三题 采药

DP

动态规划
我们知道,贪心的方法是取全局最优解,而 DP 是指通过解决局部最优解,来找到整个问题的最优解,我们来用看看下面这个求最短路的例子:
    / 2 \
1 - 3   - 5
   \ 4   /
我们求从 1 到 5 的的最短路,首先我们应该求出 1->2/3/4 的最短路,我们已经知道了 f(1) ( 1 的最短路)=1,将其移动到并算出 1->2 的最短路的过程就叫状态转移,而 f(1) 就是所谓的状态。 另外我们知道2/3/4 是同一层的东西,所以我们称这几个叫做”阶段”,1 也是一个阶段。 另外再来说说DP,需要满足的一些条件
  • 无后效性
  • 最优子结构
最优子结构是指”每个阶段的最优状态可以从之前某个阶段的某个或某些状态得到” 而无后效性是指”前面得到的解,对后面没有影响”

装箱问题

题目链接: [http://codevs.cn/problem/1014/] 首先我们第一个想到的是贪心,不过你尽管贪,能 A 算我输 我们先看代码吧qwq
#include <stdio.h>
int n,v;
int a[40],f[40][210000];
int main(){
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        for(int j=v;j>=a[i];j--){
            if(f[i-1][j-a[i]]+a[i]>f[i-1][j]) f[i][j]=f[i-1][j-a[i]]+a[i];
            else f[i][j]=f[i-1][j];
        }
        for(int j=1;j<a[i];j++) f[i][j]=f[i-1][j];
    }
    printf("%d",v-f[n][v]);
}
a[] 价格 f[i][j] 当第 i 个物品被放进来时,容量为 j 的箱子最多可以放多少. 所以我们可以很容易得到下面这个状态转移方程
f[i][j]=max( f [ i-1] [ j – a [ i ] ] + a [ i ] , f [ i – 1 ] [ j ] )
将这个方程输入进程序,你的第一道dp就完成了

循环 j ?


for(int j=v;j>=a[i];j–)
为什么 j 要倒着来?他能正这来吗? 当然是不能 如果你有心情手推你会发现,它正着来的时候会累加qwq 没错这就是完全背包,有关完全背包,我们过几次就会讲了

采药

题目链接: [https://www.luogu.org/problemnew/show/P1048] 不止这一家有这道题的说~
对比一下上面的装箱问题,我们可以发现,他们很相似,不过采药比装箱多以一个项目 – 时间 但是这显然不打扰,把 j 对应改成时间就行了 不过再让我们看看,这个二维数组,到底有没有必要
f[i][j]=max( f [ i-1] [ j – a [ i ] ] + a [ i ] , f [ i – 1 ] [ j ] )
我们只用到了 i-1 !!! 所以我们可以把方程化成下面这个
f[j]=max( f [ j – a [ i ] ] + a [ i ] , f [ j ] )
#include <cstdio>
using namespace std;
int t,m;
int time[110],pri[110],f[1100];
int main(){
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++) scanf("%d%d",&time[i],&pri[i]);
    for(int i=1;i<=m;i++){
        for(int j=t;j>=time[i];j--){
            if(f[j]<f[ j-time[i] ]+pri[i]){
                f[j]=f[ j-time[i] ]+pri[i];
            }
        }
    }
    printf("%d",f[t]);
}

01背包

说了这么多,让我们总结一下 01 背包 这种类型 针对于有一定空间,一定数量的物品,每个物品只能放一个,我们可以把他当为 01 背包,它的状态转移方程是:
f[j]=max( f [ j – a [ i ] ] + a [ i ] , f [ j ] )
]]>