StarsWhisper

89
文章
37
分类
77
标签

【背包DP练习】洛谷 P5020货币系统 P1757通天之分组背包 P1064[NOIP2006 提高组]金明的预算方案 P5322 [BJOI2019]排兵布阵.md

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

洛谷 P5020货币系统

https://www.luogu.com.cn/problem/P5020

思路是把货币从小到大排序，然后按顺序依次完全背包dp，每次dp检查i-1种面值的货币能不能凑出第i种货币
做完看了看，这个思路始终进行着令人尴尬的重复，但是懒得改了
然后去题解看了看发现没有比这还麻烦的方法
.
最后四个样例数据范围比较大，但应该都不是需要时间特别长的，而是卡一些技巧。
80分代码：修改一（不是亿）点点就可以满分

​
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long LL;
typedef std::pair<int ,int> PP;
const int N = 25005,M = 105;
int dp[N],val[M],kik[M];
int n,m,t,cnt;
int main()
{
scanf("%d",&t);
while(t–){
memset(dp,0,sizeof(dp));
memset(kik,0,sizeof(kik));
scanf("%d",&n);
for(int i=0; i<n; i++){
scanf("%d",&val[i]);
}
std::sort(val,val+n);
for(int i=1; i<n; i++){
for(int j=0; j<i; j++){
if(kik[j]) continue;
for(int k=val[j]; k<=val[i]; k++){
dp[k] = std::max(dp[k],dp[k-val[j]]+val[j]);
}
}
if(dp[val[i]] == val[i]) kik[i] = 1;
}
cnt = 0;
for(int i=0; i<n; i++){
if(!kik[i]){
cnt += 1;
}
}
printf("%d\n",cnt);
}
return 0;
}

TEL原因是 仅仅在for i 的一层循环中检查是否剔除面值i，做了很多无用功。
修改：
在for j的一层循环中，若出现面值i已经被凑出来，则不用把循环全部进行完，退出循环即可。这样可以节省一些时间
做出该修改后得分95，还是未AC
于是又在每次dp面值i之前先检查之前是否出现过可以被面值i整除的面值，有的话直接剔除，终于AC
AC代码：

​
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long LL;
typedef std::pair<int ,int> PP;
const int N = 25005,M = 105;
int dp[N],val[M],kik[M];
int n,m,t,cnt;
int main()
{
scanf("%d",&t);
while(t–){
memset(dp,0,sizeof(dp));
memset(kik,0,sizeof(kik));
scanf("%d",&n);
for(int i=0; i<n; i++){
scanf("%d",&val[i]);
}
std::sort(val,val+n);
for(int i=1; i<n; i++){
for(int j=0; j<i; j++){
if(val[i]%val[j] == 0){
kik[i] = 1;
break;
}
}
if(kik[i]) continue;
for(int j=0; j<i; j++){
if(kik[j]) continue;
for(int k=val[j]; k<=val[i]; k++){
dp[k] = std::max(dp[k],dp[k-val[j]]+val[j]);
}
if(dp[val[i]] == val[i]) break;
}
if(dp[val[i]] == val[i]) kik[i] = 1;
}
cnt = 0;
for(int i=0; i<n; i++){
if(!kik[i]){
cnt += 1;
}
}
printf("%d\n",cnt);
}
return 0;
}

洛谷 P1757 通天之分组背包

https://www.luogu.com.cn/problem/P1757
分组背包

​
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long LL;
typedef std::pair<int ,int> PP;
const int N = 1005,M = 105;

int m,n,w,v,g,gg;
struct Item
{
   int value,weight;
}gr[N][N];
int num[N],mp[N];
int dp[N];
int idx;

int main()
{
   scanf("%d%d",&m,&n);
   for(int i=0; i<n; i++){
      scanf("%d%d%d",&w,&v,&g);
      if(!mp[g]) mp[g] = ++idx;
      gg = mp[g];
      gr[gg][num[gg]].weight = w;
      gr[gg][num[gg]].value  = v;
      num[gg] += 1;
   }
   for(int i=1; i<=idx; i++){
      for(int j=m; j>=0; j--){
         for(int k=0; k<num[i]; k++){
            if(j >= gr[i][k].weight){
               dp[j] = std::max(dp[j],dp[j-gr[i][k].weight]+gr[i][k].value);
            }
         }
      }
   }
   printf("%d",dp[m]);
   return 0;
}

洛谷 P1064 [NOIP2006 提高组] 金明的预算方案

https://www.luogu.com.cn/problem/P1064

​
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long LL;
typedef std::pair<int ,int> PP;
const int N = 3.2e4+5,M = 105;
int va[N],ww[N],ex[N][3],zhu[N],dp[N];
int n,m,z,idx,tv,tz,tf,tf2;

int main()
{
   scanf("%d%d",&m,&n);
   for(int i=1; i<=n; i++){
      scanf("%d%d%d",&va[i],&ww[i],&z);
      if(z) {
         ex[z][0] += 1;
         ex[z][ex[z][0]] = i;
      }else{
         zhu[++idx] = i;
      }
   }
   for(int i=1; i<=idx; i++){
      tz = zhu[i];
      for(int j=m; j>=0; j--){
         tv = va[tz];
         if(j >= tv) dp[j] = std::max(dp[j],dp[j-tv]+ww[tz]*va[tz]);
         if(ex[tz][0]){
            tf = ex[tz][1];
            tv = va[tz] + va[tf];
            if(j >= tv) dp[j] = std::max(dp[j],dp[j-tv]+ww[tz]*va[tz]+ww[tf]*va[tf]);
         }
         if(ex[tz][0] >= 2){
            tf2 = ex[tz][2];
            tv = va[tz]+va[tf2];
            if(j >= tv) dp[j] = std::max(dp[j],dp[j-tv]+ww[tz]*va[tz]+ww[tf2]*va[tf2]);
            tv += va[tf];
            if(j >= tv) dp[j] = std::max(dp[j],dp[j-tv]+ww[tz]*va[tz]+ww[tf2]*va[tf2]+ww[tf]*va[tf]);
         }
      }
   }
   printf("%d",dp[m]);
   return 0;
}

洛谷 P5322 [BJOI2019]排兵布阵

分组背包
用dp[i] 记录总共派出i个人的时候，最大的得分
1.准备

想办法构造一个cas[][]数组 记录第i个城堡可以打败j个玩家时刚好需要多少兵力。
这样我们可以认为， 每个城堡为一组 ，每一组中有s个数据分别为:在城堡i，分别打败1,2,3…s个玩家[花费的兵力，得到的分数]

2.开始套分组背包模板

->for [1,2,3,4…n] 枚举所有的n个城堡:
…->for[m,m-1…3,2,1] 倒序枚举派遣总人数:
…/…->for[1,2,3,4…s] 枚举每个城堡的s组数据:
…/…/…->dp[w] = std::max(dp[w], dp[w-cost]+gain);

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
typedef long long int LL;
const int INF = 0x7fffffff, SCF = 0x3fffffff;
const int N = 105, M = 2e4+4, MOD =  1000000007;
int ssa[N][N];//every enemy's solders send to castle i; 
int cas[N][N];//min solders number you send when you can beat j player at castle i;
int dp/*[N]*/[M];//max score you gain when castle = i and solders = j
int s,n,m,v;
int main()
{
    scanf("%d%d%d",&s,&n,&m);
    for(int i=1; i<=s; i++){
        for(int j=1; j<=n; j++){
            scanf("%d",&ssa[j][i]);
        }
    }
    for(int i=1; i<=n; i++){
        std::sort(ssa[i]+1,ssa[i]+s+1);
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=s; j++){
            int num = (ssa[i][j]<<1)+1;
            cas[i][j] = num;
            if(num > m) break;
        }
    }
    //for(int i=0; i<M; i++) dp[i] = -SCF;
    //dp[0] = 0;
    for(int i=1; i<=n; i++){
        for(int w=m; w>=0; w--){
            for(int j=0; j<=s; j++){
                int gain = i*j, cost = cas[i][j];
                if(w-cost < 0) break;
                dp[w] = std::max(dp[w], dp[w-cost]+gain);
            }
        }
    }
    printf("%d",dp[m]);
    return 0;
}