ZJ c264: 神奇的載物任務

題目鏈接:https://zerojudge.tw/ShowProblem?problemid=c264

想了好久終於想出答案

一眼就能看出是變形的0/1背包

但多了一個力矩要處理

首先要先對力矩做處理

把最重的sort到最前面(越重排在越前面一定越好)

再來寫一個0/1背包的模板上去並把它開成二維

用以存力矩的重量限制

而力矩的計算為每放j個物品就乘j

則轉移曲線為

dp[j][k]=max(dp[j][k],dp[j-1][k-weight[i]*j]+value[i])

因為不一定能放滿L個

所以答案是

max(dp[i][j])    for i in l    for j in t

以下為code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define AC ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

int main()

{

AC

ll n,t,l;

cin>>n>>t>>l;

vector<pair<ll,ll>> vec(n);

for(ll i=0;i<n;i++)

cin>>vec[i].first>>vec[i].second;

sort(vec.begin(),vec.end(),greater<pair<ll,ll>>());

vector<vector<ll>> dp(l+1,vector<ll>(t+1,0));

for(ll i=0;i<n;i++)

for(ll j=l;j>=1;j--)

for(ll k=t;k>=vec[i].first*j;k--)

dp[j][k]=max(dp[j][k],dp[j-1][k-vec[i].first*j]+vec[i].second);

ll ans=0;

for(ll i=0;i<=l;i++)

ans=max(ans,*max_element(dp[i].begin(),dp[i].end()));

cout<<ans<<'\n';

}