今日的学习记录

DP

今天写了一点背包的题，遇到几个之前没见过的写在此作为记录

POJ - 2184

题意: n头牛，分别给定一个智力值和幽默值，要求选择其中的牛使得所有的智力值与幽默值之和最大，并且要求智力值、幽默值的和大于0

思路：转换为01背包以智力值或幽默值为体积，另一个为价值求智力值与幽默值之和的最大值，但是这两种属性存在负数，可以考虑将所有值平移，从而消去负数的影响

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n;
int f[120];
int s[120];
int dp[200000+10];
const int maxn=2e5+10;
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int sum1=0,sum2=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&f[i],&s[i]);
        }
        for(int i=0;i<=maxn;i++)dp[i]=-1e9;
        int start=1e5;
        dp[start]=0;
        for(int i=0;i<n;i++)
        {
            if(f[i]>=0)
            for(int j=maxn;j>=f[i];j--)
            dp[j]=max(dp[j],dp[j-f[i]]+s[i]);
            else for(int j=0;j<=maxn+f[i];j++)dp[j]=max(dp[j],dp[j-f[i]]+s[i]);
        }
        int ans=0;
        for(int i=start;i<=maxn;i++)
            if(dp[i]>=0)ans=max(ans,dp[i]+i-start);
        printf("%d\n",ans);
    }
    return 0;
}

HUD - 2639

题意: 给一个背包，求能达到的第k大的值

思路: dp数组多开一维存下前k大的数，在状态转移时，分别取出dp[j]与dp[j-v[i]]中的前k大的数，之后将这2k个数进行合并成前k大个数

#include<bits/stdc++.h>

using namespace std;
int n,m,k;
int v[102];
int w[102];
int q1[102];
int q2[102];
int dp[100000+10][35];
int main()
{
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<n;i++){
            scanf("%d",&w[i]);
        }
        for(int i=0;i<n;i++){
            scanf("%d",&v[i]);
        }
        memset(dp,0,sizeof(dp));
        memset(q1,-1,sizeof(q1));
        memset(q2,-1,sizeof(q2));
        for(int i=0;i<n;i++)
        for(int j=m;j>=v[i];j--){
            for(int p=1;p<=k;p++)
            {
                q1[p]=dp[j][p];
                q2[p]=dp[j-v[i]][p]+w[i];
            }
            int p1=1,p2=1,p=1;
            while(p<=k&&(p1<=k||p2<=k))
            {
                if(q1[p1]>q2[p2])
                    dp[j][p]=q1[p1++];
                else dp[j][p]=q2[p2++];
                if(dp[j][p-1]!=dp[j][p])
                    p++;
            }
        }
        printf("%d\n",dp[m][k]);
    }
    return 0;
}

POJ - 2923

题意: 有n个货物以及2俩车，车的装载量分别为c1、c2,求将所有货物搬走所需的最少次数

思路: 观察到n很小，故考虑状态压缩，将每个状态表示出来后进行一个判断，判断目前的状态能否被货车装载，可以使用01背包，dp过程时求出总重量和不超过c1的最大装载量并比较这两个重量的差是否<=c2 之后再进行dp,转移时判断两个状态是否重合

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;
int n,c1,c2;
int a[20];
int ok[2000];
int dp[2000];
int tmp[2000];
int main()
{
    int T;scanf("%d",&T);
    int tot=0;
    while(T--)
    {
        scanf("%d%d%d",&n,&c1,&c2);
        for(int i=0;i<n;i++)scanf("%d",&a[i]);
        int len=0;
        for(int i=0;i<(1<<n);i++)
        {
            dp[i]=1e9;
           memset(tmp,0,sizeof(tmp));
            int sum=0;
            for(int j=0;j<n;j++)
            {
                if(i&(1<<j))
                {
                    sum+=a[j];
                    for(int k=c1;k>=a[j];k--)
                        tmp[k]=max(tmp[k],tmp[k-a[j]]+a[j]);
                }
            }
            int flag=0;
            for(int j=c1;j>=0;j--)
            if(sum-tmp[j]<=c2)
            {
                flag=1;
                break;
            }
            if(flag)
            ok[len++]=i;
        }
        dp[0]=0;
        for(int i=0;i<len;i++)
            for(int j=0;j<(1<<n);j++)
            if((ok[i]&j)==0)
            {
                dp[ok[i]|j]=min(dp[ok[i]|j],dp[j]+1);
            }
        printf("Scenario #%d:\n",++tot);
        printf("%d\n",dp[(1<<n)-1]);printf("\n");
    }
    return 0;
}