首页 > itarticle > 洛谷p1455,p1926,p1064,p1757题解 P1926 小书童——刷题大军 P1064 金明的预算方案 P1757 通天之分组背包

洛谷p1455,p1926,p1064,p1757题解 P1926 小书童——刷题大军 P1064 金明的预算方案 P1757 通天之分组背包

admin 11月 23, 2020 0

简要题意：去商店用不超过w的钱买到价值最大的商品，并且有的商品会捆绑销售。

思路：

  • 因为存在捆绑销售，我们不妨把捆绑在一起的商品合成一种商品，这里用并查集或者dfs都可以实现。
  • 然后做一次01背包便可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 

using namespace std;
typedef long long ll;
const int maxn = 1e4+10;
int n,m,w;
int c[maxn],d[maxn];
vector<int> g[maxn];
int sumc,sumd;
bool vis[maxn];
void (int u){
    vis[u]=1;
    sumc+=c[u],sumd+=d[u];
    for(auto v:g[u]){
        if(!vis[v])dfs(v);
    }
}
int n1;
int ct[maxn],wt[maxn];
int dp[maxn];
int main(){
    scanf("%d%d%d",&n,&m,&w);
    for(int i=1;i<=n;i++){
        scanf("%d%d",c+i,d+i);
    }
    int u,v;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            sumc=sumd=0;
            dfs(i);
            ct[++n1]=sumc;
            wt[n1]=sumd;
        }
    }
    for(int i=1;i<=n1;i++){
        for(int j=w;j>=ct[i];j--){
            dp[j]=max(dp[j],dp[j-ct[i]] + wt[i]);
        }
    }
    cout<<*max_element(dp,dp+1+w);
    return 0;
}

P1926 小书童——刷题大军

较简单，可自己尝试。

P1064 金明的预算方案

简要题意：商店里有主件和配件，买配件必须买主件，配件不会再拥有配件，问不超过最大花费的情况下可得到的最大价值。

思路：

  • 根据数据范围我们发现配件只有最多2个，不妨设5种状态，分别为：
    • 什么都不买
    • 只买主件
    • 买主件和第一个配件
    • 买主件和第二个配件
    • 全买
  • 那么就变成了一个01背包模板题了。
  • 分别对状态进行转移便可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 

using namespace std;
typedef long long ll;
const int maxn = 40000;
int n,m;
int v,p,q;
int c[65][4];
int w[65][4];
int dp[2][maxn];
int pre=0,now=1;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&v,&p,&q);
        if(q==0){
            c[i][0]++;
            c[i][1]=v;
            w[i][1]=p*v;
        }
        else{
            c[q][0]++;
            if(c[q][2]){
                c[q][3]=v;
                w[q][3]=p*v;
            }
            else{
                c[q][2]=v;
                w[q][2]=p*v;
            }
        }
    }
    for(int i=1;i<=m;i++){
        if(c[i][0]==0)continue;
        if(c[i][0]>=1){
            for(int j=n;j>=1;j--){
                dp[now][j]=max(dp[now][j],dp[pre][j]);
                if(j-c[i][1]>=0){
                    dp[now][j]=max(dp[now][j],dp[pre][j-c[i][1]] + w[i][1]);
                }
            }
        }
        if(c[i][0]>=2){
            for(int j=n;j>=1;j--){
                dp[now][j]=max(dp[now][j],dp[pre][j]);
                if(j-c[i][1]-c[i][2]>=0){
                    dp[now][j]=max(dp[now][j],dp[pre][j-c[i][1]-c[i][2]] + w[i][1]+w[i][2]);
                }
            }
        }
        if(c[i][0]==3){
            for(int j=n;j>=1;j--){
                dp[now][j]=max(dp[now][j],dp[pre][j]);
                if(j-c[i][1]-c[i][3]>=0){
                    dp[now][j]=max(dp[now][j],dp[pre][j-c[i][1]-c[i][3]] + w[i][1]+w[i][3]);
                }
                if(j-c[i][1]-c[i][2]-c[i][3]>=0){
                    dp[now][j]=max(dp[now][j],dp[pre][j-c[i][1]-c[i][2]-c[i][3]] + w[i][1]+w[i][2]+w[i][3]);
                }
            }
        }
        now^=1;pre^=1;
    }
    int ans=0;
    for(int i=0;i<=n;i++)ans=max(ans,dp[pre][i]);
    cout<<ans;
    return 0;
}

P1757 通天之分组背包

简要题意：分组背包，同一类型最多买一种，问最大价值。

思路：

  • 直接分组，同一组内由前一组转移得到，然后就能直接当作01背包做了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 

using namespace std;
typedef long long ll;
vector<pair<int,int> >p[105];
const int maxn = 1005;
int dp[2][maxn];
int pre=0,now=1;
int main(){
    int m,n;
    int a,b,c;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a,&b,&c);
        p[c].push_back(make_pair(a,b));
    }
    int ans=0;
    for(int q=1;q<=100;q++){
        for(auto e:p[q]){
            for(int i=m;i>=0;i--){
                dp[now][i]=max(dp[pre][i],dp[now][i]);
                if(i-e.first>=0)
                dp[now][i]=max(dp[now][i],dp[pre][i-e.first]+e.second);
                ans = max(ans , dp[now][i]);
            }
        }
        now^=1;pre^=1;
    }
    cout<<ans;
    return 0;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能