2019 CSP-J 题解

前言

咕咕咕了好久,终于今天把 T3 的坑给补回来了,于是打算写一波题解。

勿吐槽码风,丑是必然的,毕竟好久前写的代码了。

T1 数字游戏

P5660 数字游戏

大意:给定长度为 8 的 01 串,求 1 的个数

sb 题,考察字符串基本使用,当时好像 2:30 还没到就已经切完了

考场代码:

#include <iostream>
#include <cstdio>
#include <string>
//#define LOCAL

using namespace std;

int main()
{
#ifndef LOCAL
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
#endif
    string s;
    cin>>s;
    int ans=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='1') ans++;
    }
    printf("%d\n",ans);
    return 0;
}

T2 公交换乘

P5661 公交换乘

大意:坐一次地铁可以获取一张有效期 45 分钟的优惠券,可以凭券免费坐票价不超过地铁票价的公交车,优惠票可累积,使用时优先使用最先获得的

模拟即可,这里使用 vector 模拟优惠票的队列,代码并不优美但是能过。

坑点就在于

  • 使用票要使用最先获得的
  • 优惠票用过要删掉

记得当时在考场上发现队列不能用之后还自己研究 vector::erase 的用法

#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
//#define LOCAL
struct ticket{
    int price;
    ll time;
};
vector<ticket> q;

int main()
{
#ifndef LOCAL
    freopen("transfer.in","r",stdin);
    freopen("transfer.out","w",stdout);
#endif
    int n;
    scanf("%d",&n);
    ll ans=0;
    while(n--)
    {
        int type,price;
        ll t;
        scanf("%d %d %lld",&type,&price,&t);
        if(type==0)//如果坐地铁
        {
            ans+=price;//更新答案
            ticket tt={price,t};
            q.push_back(tt);//插入候选队
        }
        else if(type==1)//如果是公交
        {
            while(!(q.empty())&&t-q.front().time>45) q.erase(q.begin());//先删掉超时的优惠票
            bool flag=0;
            for(int i=0;i<q.size();i++)//查询符合标准的第一张优惠票
            {

                if(q[i].price>=price)
                {
                    q.erase(q.begin()+i);//直接删掉
                    flag=1;
                    break;
                }
            }
            if(!flag) ans+=price;//如果不存在就需要付原价
        }
    }
    printf("%lld\n",ans);
    return 0;
}

T3 纪念品

P5662 纪念品

谁叫我太菜,当时考场上骗了 10 分走人,现在看题解才写出正解。

大意:T 天,N 种纪念品,每天不同的纪念品都有不同的价格,小伟一开始有 M 金币,每天可以卖掉手中的纪念品换取金币,买进纪念品花费金币或者什么都不做。在第 T 天一定会卖出手中所有纪念品,求最高收益

分析题意,可以发现需要使用 dp,发现状态貌似很复杂,又可以买进又可以卖出,然而,注意到买进和卖出都可以进行无数次,因此我们可以把所谓一直持有的纪念品看成先将其卖出,又将其买进,效果是一样的,实质上就是每一天都做一次完全背包。

f_{i,j,k} 表示第 i 天,考虑前 j 种物品,手里有 k 金币时,在下一天全部卖出能达到的最大收益,则有方程

f_{i,j,k}=\max(f_{i,j,k},f_{i,j-1,k+p_i,j}+p_{i,j}-p_{i+1,j})

表示如果要了第 j 个物品,那么净收益即为 p_{i,j}-p_{i+1,j},从 f_{i,j-1,k+p_i,j} 转移而来,利用完全背包思想压一下维度然后改循环顺序即可以达到正确结果。

(第一维的天数是可以不要的,第二维的物品也是可以用滚动数组优化掉的,保留第三维即可)

#include <cstdio>
#include <cctype>
#include <cstring>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

int n,t,p[105][105],f[10005];

int main()
{
    t=read(),n=read();
    int m=read();
    for(int i=1;i<=t;i++)
        for(int j=1;j<=n;j++)
            p[i][j]=read();
    int ans=m;
    for(int i=1;i<t;i++)
    {
        memset(f,~0x3f,sizeof(f));//先赋负无穷
        f[ans]=ans;//初始值,什么都不干的情况
        for(int j=1;j<=n;j++)//枚举物品,从小到大即为完全背包
            for(int k=ans;k>=p[i][j];k--)//枚举金钱
                f[k-p[i][j]]=max(f[k-p[i][j]],f[k]+p[i+1][j]-p[i][j]);
        int maxn=0;//统计最优答案用
        for(int j=0;j<=ans;j++)
            maxn=max(maxn,f[j]);
        ans=maxn;
    }
    printf("%d\n",ans);
    return 0;
}

T4 加工零件

P5663 加工零件

大意:一个工厂正在生产零件,工人从 1 到 n 标号,某些工人之间有双向传送带。

如果 x 号工人想生产一个被加工到第 L (L \gt 1) 阶段的零件,则所有与 x 号工人有传送带直接相连的工人,都需要生产一个被加工到第 L – 1 阶段的零件(但 x 号工人自己无需生产第 L – 1 阶段的零件)。

如果 x 号工人想生产一个被加工到第 1 阶段的零件,则所有与 x 号工人有传送带直接相连的工人,都需要为 x 号工人提供一个原材料。

给定一些工单,即需要某工人生产某阶段的零件,求 1 号是否需要提供原材料。


先将其抽象成图论问题,以工人为节点,传送带为边来建图。

考虑暴力,虽然一定超时,但还是能给我们一些启示,不难发现暴力就是在看 a 与 1 之间是否存在长度为 L 的路径,同时我们又注意到:如果 L 为奇数,且从 1 到 a 存在一条奇数路径,且最小奇数路径长小于等于 L,那么 1 就必须提供原材料(为什么可以:你可以两个传送带之间来回跳,比如 1->2->1->2->1…,但如果最小的奇数路径大于 L,说明从 aL 个阶段也轮不到 1,就不行)同样的,如果 L 为偶数,且从 1 到 a 存在一条偶数路径,且最小偶数路径长小于等于 L,那么 1 就必须提供原材料。

这就给我们了正解的方法:找到每个点距离 1 点的最小奇数路径与偶数路径即可,这一过程实现可以使用 bfs(因为我当时还没学过最短路),然后判定每一个工单的时候按照奇偶数去找最短奇偶路径是否小于等于工单给定阶段就可以判定 YesNo

当然,我写的考场代码有一个小 bug,就是没有判断 1 点不连通的情况,然而 ccf 的数据没有这种特殊情况,所以也就 A 了这道题

考场代码:

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
//#define LOCAL
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
vector<int> g[100020];//存图
bool vis0[100020],vis1[100020];//bfs用
int minans0[100020],minans1[100020];//存储奇偶最短路
struct node{
    int n,time;
};
queue<node> q;
void bfs()
{
    memset(minans0,inf,sizeof(minans0));
    memset(minans1,inf,sizeof(minans1));
    q.push((node){1,0});
    while(!q.empty())
    {
        int curn=q.front().n;//当前的点
        int nxtc=q.front().time+1;//下一个点会经过的路径长
        q.pop();
        for(int i=0;i<g[curn].size();i++)
        {
            int nxt=g[curn][i];
            if(nxtc%2==0)//如果下一个点是偶数到达
            {
                if(vis0[nxt]==0)//如果未访问
                {
                    vis0[nxt]=1;
                    q.push((node){nxt,nxtc});
                    minans0[nxt]=min(nxtc,minans0[nxt]);//就更新这里的结果
                    //cout<<"no."<<nxt<<" "<<nxtc<<endl;
                }
            }
            if(nxtc%2==1)//反之如果是奇数,也一样
            {
                if(vis1[nxt]==0)
                {
                    vis1[nxt]=1;
                    q.push((node){nxt,nxtc});
                    minans1[nxt]=min(nxtc,minans1[nxt]);
                    //cout<<"no."<<nxt<<" "<<nxtc<<endl;
                }
            }
        }
    }
    return;
}

void add_edge(int u,int v)
{
    g[u].push_back(v);//注意是无向图
    g[v].push_back(u);
    return;
}


int main()
{
#ifndef LOCAL
    freopen("work.in","r",stdin);
    freopen("work.out","w",stdout);
#endif
    int n,m,q;
    scanf("%d %d %d",&n,&m,&q);
    while(m--)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        add_edge(u,v);
    }
    bfs();//预处理
    while(q--)
    {
        int a,l;
        scanf("%d %d",&a,&l);
        bool flag=0;
        if(l%2==0&&vis0[a]==1&&minans0[a]<=l) flag=1;//如果是偶数阶段并且能到达
        if(l%2==1&&vis1[a]==1&&minans1[a]<=l) flag=1;
        if(flag) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

解题报告 P1336 最佳课题选择

题目内容

P1336

一共写 n 篇论文,一共 m 个课题,对于第 i 个课题如果写 x 篇则需花费 A_i\times x^{B_i} 的时间,求最小时间

解题思路

泛化物品的背包,价值随着分给他的大小而变化。由于数据范围比较小,所以直接枚举第 i 个课题选择的数量 k 即可,转移方程:

f_{i,j}=\min(f_{i,j},f_{i-1,j-k}+A_i\times k^{B_i})

然后边界就是 f_{1,i}=A_1\times i^{B_1},最后使用滚动数组优化一下即可

不开 long long 见祖宗

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
typedef long long ll;

ll n,m,a[25],b[25],f[205];

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline ll min(ll a,ll b)
{
    return a<b?a:b;
}

inline ll ksm(ll base,ll p)//写了个快速幂
{
    ll ans=1;
    for(;p;p>>=1)
    {
        if(p&1)
            ans*=base;
        base*=base;
    }
    return ans;
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
        a[i]=read(),b[i]=read();
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++)
        f[i]=a[1]*ksm(i,b[1]);
    //边界
    for(int i=2;i<=m;i++)
        for(int j=n;j>=0;j--)
            for(int k=0;k<=j;k++)
                f[j]=min(f[j],f[j-k]+a[i]*ksm(k,b[i]));//进行转移
    printf("%lld\n",f[n]);
    return 0;
}

解题报告 P1941 飞扬的小鸟

虽说 AFO 了,但是我做下题总还是可以的吧我不想学文化课

题目内容

flappy bird 的改编题,地图为 n\times m,分别是长和高。每秒钟内可以点击多次屏幕,在第 i 位置处点击一次屏幕可以在下一秒上升 x_i 格,不点击屏幕下降 y_i 格,不能碰到管道或者触底(高度为 0),求如果可以通过游戏的最小点击屏幕次数或不可以通过游戏的话最多通过的管道数。

解题思路

考虑 f_{i,j} 表示到达 (i,j) 的最少点击次数,如不能到达用 INF 表示。

于是可以将状态的转移抽象成背包,每次可以选择点击无数次或者下降一次,转移方程如下:

f_{i,j}=\min(f_{i,j-x_i},f_{i-1,j-x_i})+1

这是上升来的,意义就是从前一秒的状态点击一次或者从当前秒再点击一次取最优

f_{i,j}=\min(f_{i,j},f_{i-1,j+y_i})

这就是下降来的

这题需要注意的地方:

  • 上升的过程是一个完全背包(可以点击屏幕无限次),下降的是 0-1 背包
  • 有可能会飞出去(大于 m),这个时候要特判,将其还原

我使用了结构体封装地图的每一格,包含了是否有管道,下降/上升的高度以及最高能通过的高度以及最低能通过的高度。

最后统计答案的时候如果不能过,那就从最后往前寻找第一个能过的点,然后统计前面有多少管道

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define a(x) game[x]
using namespace std;

const int maxn = 10005, INF = 0x3f3f3f3f;
int n, m, k;
int f[maxn][3005];

struct node
{
    int x, y, high, low;
    bool flag;
} game[maxn];

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int main()
{
    n = read(), m = read(), k = read();
    for (int i = 1; i <= n; i++)
    {
        a(i).x = read(), a(i).y = read();
        a(i).high = m, a(i).low = 1;
    }
    int p, l, h;
    for (int i = 1; i <= k; i++)
    {
        p = read(), l = read(), h = read();
        a(p).flag = 1,
        a(p).high = h - 1,
        a(p).low = l + 1;
    }
    memset(f, INF, sizeof(f));
    for (int i = 1; i <= m; i++)
        f[0][i] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = a(i).x + 1; j <= m + a(i).x; j++)
            f[i][j] = min(f[i][j], min(f[i][j - a(i).x] + 1, f[i - 1][j - a(i).x] + 1));
        for (int j = m; j <= m + a(i).x; j++)
            f[i][m] = min(f[i][m], f[i][j]);
        for (int j = 1; j <= m - a(i).y; j++)
            f[i][j] = min(f[i][j], f[i - 1][j + a(i).y]);
        for (int j = 1; j < a(i).low; j++)
            f[i][j] = INF;
        for (int j = m; j > a(i).high; j--)
            f[i][j] = INF;
    }
    int ans = INF;
    for (int i = 1; i <= m; i++)
        ans = min(ans, f[n][i]);
    if (ans < INF)
    {
        printf("1\n%d\n", ans);
        return 0;
    }
    for (int i = n - 1; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            if (f[i][j] < INF)
            {
                ans = 0;
                for (int t = 1; t <= i; t++)
                    if (a(t).flag)
                        ans++;
                printf("0\n%d\n", ans);
                return 0;
            }
}

解题报告 P1802 5倍经验日

题目内容

P1802

大意:现有 n 个好友可以打,有 x 瓶药水,每个好友有 lose_iwin_iuse_i 三个参数,分别表述了打输能获得多少经验,打赢能获得多少经验,需要多少瓶药水才打赢(如果使用的药水更少则赢不了),求最大能获得的经验乘五的值

解题思路

第一遍做的时候,想到的状态定义是 f_{i,j} 表示前 i 个人消耗 j 瓶药水能达到的最大经验,观察发现这个定义满足无后效性和最优子结构,所以开始想方程式。很明显,当我们面临一个人的时候,有两种决策:打——不打,而如果当前药品不够打的话肯定不能打,这里我枚举了使用的药量,但是没必要,这个不开 long long 的代码取得了 90 分的好成绩

#include <cstdio>

const int maxn=1e3+5;
int n,x,lose[maxn],win[maxn],use[maxn],f[maxn][maxn];

inline int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    scanf("%d %d",&n,&x);
    for(int i=1;i<=n;i++)
        scanf("%d %d %d",lose+i,win+i,use+i);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=x;j++)
        {
            for(int k=0;k<use[i];k++)
                f[i][j]=max(f[i][j],f[i-1][j-k]+lose[i]);
            if(j>=use[i])
                f[i][j]=max(f[i][j],f[i-1][j-use[i]]+win[i]);
        }
    printf("%d\n",f[n][x]*5);
    return 0;
}

然后仔细想想,发现其实这个可以进行优化,由于如果当前药量打不过的时候放多少药都没用,所以可以索性不放药,得到的答案也是正确的,同时,其实当药够打的时候,也是要考虑打还是投降两种情况的,并且空间的第一维可以像 0-1 背包一样优化掉。经过修改后的转移方程和代码如下:

f_j=\begin{cases}
\max(f_j+lose_i,f_{j-use_i}+win_i)\quad(j\ge use_i)\
f_j+lose_i\quad(j<use_i)
\end{cases}

#include <cstdio>
typedef long long ll;

const int maxn=1e3+5;
ll n,x,lose[maxn],win[maxn],use[maxn],f[maxn];

inline ll max(ll a,ll b)
{
    return a>b?a:b;
}

int main()
{
    scanf("%lld %lld",&n,&x);
    ll ans=0;
    for(int i=1;i<=n;i++)
        scanf("%lld %lld %lld",lose+i,win+i,use+i);
    for(int i=1;i<=n;i++)
        for(int j=x;j>=0;j--)
        {
            if(j<use[i])
                f[j]+=lose[i];
            else
                f[j]=max(f[j]+lose[i],f[j-use[i]]+win[i]);
            ans=max(ans,f[j]);
        }
    printf("%lld\n",ans*5);
    return 0;
}

解题报告 P2014 [CTSC1997]选课

题目内容

P2014

大意:选课,其中选某些课必须选一个先修课,每门课有一个学分,求选 m 门课达到的最大学分

解题思路

树上的 0-1 背包问题,具体的思路还是递归求解每一棵子树的最优解。

f_{now,j} 表示以 now 节点为根的子树选 j 门课(包括 now 本身)能达到的最大学分。则有状态转移方程

f_{now,j}=\max\lbrace f_{now,j},f_{x,k}+f_{now,j-k} \rbrace

其中 xnow 的儿子节点,k\in[0,j)j\in[1,m+1]

还有一点需要注意的是我们可以假设出一个 0 节点,作为整棵树的根,方便进行处理。

#include <cstdio>
#include <vector>
#include <cctype>
using namespace std;

const int maxn=305;
int n,m,s[maxn],f[maxn][maxn];
vector<int> son[maxn];

inline int read()
{
    bool w=0;
    int x=0;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            w=1;
        c=getchar();
    }
    while(isdigit(c))
        x=x*10+c-'0',c=getchar();
    return w?-x:x;
}

void dfs(int now)
{
    for(auto i:son[now])
    {
        dfs(i);
        for(int j=m+1;j>=1;--j)
            for(int k=0;k<j;++k)
                f[now][j]=max(f[now][j],f[now][j-k]+f[i][k]);//转移
    }
    return;
}

int main()
{
    n=read(),m=read();
    for(int i=1,k;i<=n;i++)
    {
        k=read(),s[i]=read();
        f[i][1]=s[i];//初始值
        son[k].push_back(i);
    }
    dfs(0);
    printf("%d\n",f[0][m+1]);
    return 0;
}

解题报告 P1077 摆花【NOIP2012PJT3】

题目内容

P1077

大意:现要摆 m 盆花,一共 n 种花,从种类编号小到大摆,每种花最多摆 a_i 盆,求方案数

解题思路

此题抽象出来后可看作多重背包问题求方案数,每盆花的价值是 1,求装满 m 的方案数。

#include <cstdio>

const int p=1000007;
int n,m,f[105],w[1005];

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    scanf("%d %d",&n,&m);
    int x;
    for(int i=1;i<=n;i++)
        scanf("%d",w+i);
    f[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=1;k<=min(w[i],j);k++)//枚举这种花的数量
                f[j]=(f[j]%p+f[j-k]%p)%p;
    printf("%d\n",f[m]);
    return 0;
}

解题报告 P1832 A+B Problem(再升级)(质数和方案)

题目内容

P1832

大意:求 n 被分解成若干个素数之和的方案总数

解题思路

打表出奇迹其实这东西不用完全打表,但是打质数表还是很重要的。

思路就是将 [1,n] 间的质数打出表,然后进行完全背包的求方案数即可,抽象的模型就是有 tot 件物品,每件物品的重量为这个质数的值,然后可以取无限次,求能凑出 n 重量的方案数。

不开 long long 见祖宗

#include <cstdio>
#include <cstring>
typedef long long ll;

const int maxn=1100;
ll n,f[maxn];
bool isprime[maxn];
int tot,prime[maxn];//tot为质数的个数,prime为质数的表。

void make_prime()//埃氏筛即可
{
    memset(isprime,1,sizeof(isprime));
    isprime[1]=isprime[0]=0;
    for(int i=2;i<=n;i++)
    {
        if(!isprime[i]) continue;
        for(int j=2;i*j<=n;j++) isprime[i*j]=0;
    }
    for(int i=2;i<=n;i++)
        if(isprime[i])
            prime[++tot]=i;
    return;
}

int main()
{
    scanf("%lld",&n);
    make_prime();
    f[0]=1;//一定记得初始值
    for(int i=1;i<=tot;i++)
        for(int j=prime[i];j<=n;j++)
            f[j]+=f[j-prime[i]];//求方案数的转移方程
    printf("%lld\n",f[n]);
    return 0;
}

解题报告 P1417 烹调方案

题目内容

P1417

大意:有 n 种食物,每种食物有 a_ib_ic_i 三个参数,定义 t 时刻烹饪完成食物时食物的美味度为 a_i-b_it,烹饪一个食物需要 c_i 时间,求 t 时间内能达到的最大美味度。

解题思路

如果不考虑 b 这个参数的话,他就是一个裸的 0-1 背包,但是由于 b 参数的存在,就需要考虑烹饪食物的顺序对结果的影响。下面进行推导:

设我们在比较两个相邻的食物 xy,当前的时刻为 p,则如果先做 x 再做 y 的话总的美味度是

\begin{aligned}
&a_x-(c_x+p)b_x+a_y-(c_y+c_x+p)b_y\
=&a_x+a_y-b_xc_x-b_yc_y-b_yc_x-b_xp-by_p
\end{aligned}

反之如果先做 y 的话:

\begin{aligned}
&a_y-(c_y+p)b_y+a_x-(c_y+c_x+p)b_x\
=&a_x+a_y-b_xc_x-b_yc_y-b_xc_y-b_xp-by_p
\end{aligned}

假设现在需要先做 x 达到的美味程度最大,则

\begin{aligned}
a_x+a_y-b_xc_x-b_yc_y-b_yc_x-b_xp-by_p>&a_x+a_y-b_xc_x-b_yc_y-b_xc_y-b_xp-by_p\
b_yc_x>&b_xc_y
\end{aligned}

因此在背包之前需要先给食物进行排序,然后再背包。

然后可能炸 int,要上 long long

#include <cstdio>
#include <algorithm>
using std::sort;
using std::max;
typedef long long ll;

int n,t,f[100005];

struct food
{
    ll a,b,c;
}x[55];

bool cmp(food a,food b)
{
    return (ll)a.c*(ll)b.b<(ll)b.c*(ll)a.b;
}

int main()
{
    scanf("%d %d",&t,&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&x[i].a);
    for(int i=1;i<=n;i++)
        scanf("%lld",&x[i].b);
    for(int i=1;i<=n;i++)
        scanf("%lld",&x[i].c);
    sort(x+1,x+n+1,cmp);
    for(int i=1;i<=n;i++)
        for(int j=t;j-x[i].c>=0;j--)
            f[j]=max((ll)f[j],f[j-x[i].c]+x[i].a-j*x[i].b);
    int ans=0;
    for(int i=1;i<=t;i++)
        ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}

解题报告 P1759 通天之潜水

题目内容

P1759

在猴王的帮助下,小 A 终于走出了这篇荒山,却发现一条波涛汹涌的河拦在了自己的面前。河面上并没有船,但好在小 A 有 n 个潜水工具。由于他还要背重重的背包,所以他只能背 m 重的工具,又因为他的力气并不是无限的,河却很宽,所以他只能背有 v 阻力的工具。但是这条河下有非常重要的数据,所以他希望能够停留的时间最久。于是他找到了你,让你告诉他方案。

大意:0-1 背包,两层限制条件,要求输出方案

解题思路

乍一看,是一个二维的背包问题,还要求输出他的方案,天哪好难,但实际上这题并不难(毕竟是黄题)。思路和榨取 kkksc03 那道题基本类似,唯一不同的是需要记录方案,而且要求字典序尽量的小

回忆:在进行前面的背包问题的时候,是如何判断选与不选的:f[j-w[i]]+c[i] 说明是要选这个物品,而我们现在既然要记录方案,那就只需要在当 f[j-w[i]]+c[i] 更大时记录一下,这个容量下的第 x 个物品被选择了,然后最后输出的时候递推回去就可以了。

这个问题里面,令 g[i][m][v]i 个物品在当前重量为 m,阻力为 v 的时候有没有选,然后最后判断的时候倒序递推,正序输出。

int cnt=0;
    for(int i=n;i>=1;i--)//从最后一个物品开始递推
    {
        if(g[i][m][v])//如果当前状态选了
        {
            ans[cnt++]=i;//记录
            m-=a[i];//回溯上一个状态的 m
            v-=b[i];//回溯上一个状态的 v
        }
    }
    for(int i=cnt-1;i>=0;i--)
        printf("%d ",ans[i]);

还有一点要注意的是需要输出字典序尽可能小的物品,所以在 if(f[j-a[i]][k-b[i]]+c[i]>f[j][k]) (判断选不选物品)的时候必须是大于号,这样才能保证尽量选前面的物品。

#include <cstdio>

int n,m,v,a[105],b[105],c[105],f[205][205];//f 用来进行 dp
bool g[105][205][205];//存储物品的选择
int ans[105];

int main()
{
    scanf("%d %d %d",&m,&v,&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d %d",a+i,b+i,c+i);
    for(int i=1;i<=n;i++)
        for(int j=m;j>=a[i];j--)//常规二维 0-1 背包
            for(int k=v;k>=b[i];k--)
                if(f[j-a[i]][k-b[i]]+c[i]>f[j][k])//注意必须是大于号,否则 WA#2
                    f[j][k]=f[j-a[i]][k-b[i]]+c[i],g[i][j][k]=1;//如果选这个物品可以更优,则进行更新并记录方案
    printf("%d\n",f[m][v]);//先把最优结果输出
    int cnt=0;
    for(int i=n;i>=1;i--)//从最后一个物品开始递推
    {
        if(g[i][m][v])
        {
            ans[cnt++]=i;
            m-=a[i];
            v-=b[i];
        }
    }
    for(int i=cnt-1;i>=0;i--)
        printf("%d ",ans[i]);
    return 0;
}

解题报告 P1164 小 A 点菜

题目内容

P1164

一个餐馆,n 种菜,每种菜只有一份,价值为 a_i 元,求刚好花完 m 元的方案总数。

解题思路

具体的思路就是,可以通过前面一个状态转移

f(i,x) 表示选了前 i 个物品后当前钱为 x 的方案个数,则有状态转移方程

f(i,x)=f(i-1,x)+f(i-1,x-a_i)

就是当前状态的方案数,可以选,可以不选,假设不选,那就有 f(i-1,x) 个方案,如果要选,那就有 f(i-1,x-a_i) 个方案,只需要两个方案数加起来即可,初始值 f(0,0) 设为 1 即可,然后第一维是可以滚动掉的,所以最终的转移方程是 f[j]+=f[j-a[i]]

#include <cstdio>

int n,m,a[105],f[10005];

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    f[0]=1;//赋初始值
    for(int i=1;i<=n;i++)
        for(int j=m;j>=a[i];j--)//同样需要从大到小进行循环
            f[j]+=f[j-a[i]];//进行递推
    printf("%d\n",f[m]);//输出最终结果
    return 0;
}