HDU5543-DP

题目链接

HDU5543

题目大意

给出金条的长度和价值还有一个可以放的长度len，求最大的价值，其中只要金条的中心再len中就可以放上去。

思路

01背包的变形，但是不同的就是两端的处理，所以我们开一个dp[N][3]来存储状态，分别表示

dp[i][0] ~ 两端都没有放
dp[i][1] ~ 一端放了金条
dp[i][2] ~ 两端放了金条

然后转移即可

for(int j=m;j>=len/2;j--){
    if(j>=len) {
        dp[j][0] = max(dp[j][0], dp[j - len][0] + val);//单纯的01背包
        dp[j][1] = max(dp[j][1], dp[j - len][1] + val);
        dp[j][2] = max(dp[j][2], dp[j - len][2] + val);
    }
    if(j>=len/2) {
        dp[j][1] = max(dp[j][1],dp[j-len/2][0]+val);//  放一端的01背包，
        dp[j][2] = max(dp[j][2],dp[j-len/2][1]+val);//  放两端的背包
    }
    ans = max(ans,dp[j][0]);
    ans = max(ans,dp[j][1]);
    ans = max(ans,dp[j][2]);
}

需要注意的是奇数除以2会有余数，所以我们让所有长度都乘上2，然后再进行转移

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 2e3+10;
ll dp[N<<1][3];
vector<pair<ll,ll>>vp;
void solve(int t){
    memset(dp,0,sizeof(dp));
    vp.clear();
    int n,m;
    scanf("%d%d",&n,&m);
    m*=2;
    ll ans = 0;
    for(int i=1;i<=n;i++){
        ll v,l;
        scanf("%lld%lld",&l,&v);
        ans = max(ans,v);
        l*=2;
        vp.push_back({l,v});
    }
    for(int i=0;i<vp.size();i++){
        ll val = vp[i].second;
        ll len = vp[i].first;
        for(int j=m;j>=len/2;j--){
            if(j>=len) {
                dp[j][0] = max(dp[j][0], dp[j - len][0] + val);//单纯的01背包
                dp[j][1] = max(dp[j][1], dp[j - len][1] + val);
                dp[j][2] = max(dp[j][2], dp[j - len][2] + val);
            }
            if(j>=len/2) {
                dp[j][1] = max(dp[j][1],dp[j-len/2][0]+val);//  放一端的01背包，
                dp[j][2] = max(dp[j][2],dp[j-len/2][1]+val);//  放两端的背包
            }
            ans = max(ans,dp[j][0]);
            ans = max(ans,dp[j][1]);
            ans = max(ans,dp[j][2]);
        }
    }
    printf("Case #%d: %lld\n",t,ans);
}
int main(){
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)solve(i);
}