題目描述

Bob 來到一家現(xiàn)購自運(yùn)商店，將 n 件商品放入了他的手推車，然后到收銀臺(tái) 付款。每件商品由它的價(jià)格 pi 和收銀員掃描它的時(shí)間 ti 秒定義。當(dāng)收銀員正在掃 描某件商品時(shí)，Bob 可以從他的手推車中偷走某些其它商品。Bob 需要恰好 1 秒 來偷走一件商品。Bob 需要付給收銀員的最少錢數(shù)是多少？請(qǐng)記住，收銀員掃描 商品的順序由 Bob 決定。

輸入格式

輸入第一行包含數(shù) n（1≤n≤2000）。接下來 n 行每行每件商品由 一對(duì)數(shù) ti，ci（0≤ti≤2000，1≤ci≤10^9）描述。如果 ti 是 0，那么當(dāng)收銀員掃描 商品i時(shí)，Bob 不能偷任何東西。

輸出格式

輸出一個(gè)數(shù)字——Bob需要支付的最小金額是多少。

樣例輸入

4
2 10
0 20
1 5
1 3

樣例輸出

8

題解

這道題可以看成是一個(gè)背包問題來做即可。
我們將總時(shí)間看成是將所有物品都交給收銀員掃描的情況下需要的時(shí)間，每一件物品的體積v[i]看作是偷取這件物品所需要的時(shí)間+掃描時(shí)間，因?yàn)槲覀冞x取一件物品后這件物品就不會(huì)再被掃描了。這樣我們就可以得到我們能夠賺取的最大金額，再用所有物品的總價(jià)值減去這個(gè)最大金額就可以得到答案了。

#include<bits/stdc++.h>
#define maxn 5005
using namespace std;
inline char get(){
    static char buf[300000],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,300000,stdin),p1==p2)?EOF:*p1++; 
}
inline long long read(){
    register char c=get();register long long f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
long long n;
long long t[maxn],c[maxn];
//?????????? 
long long V,C;
long long v[maxn];
long long dp[2005*4005];
int main(){
    //freopen("1.txt","r",stdin);
    n=read();
    long long out=0;
    for(register long long i=1;i<=n;i++)t[i]=read(),c[i]=read(),v[i]=t[i]+1,V+=t[i],C+=c[i];
    //V+=n;
    long long note=0;
    for(register long long i=1;i<=n;i++){
        for(register int j=V;j>=v[i];j--){
            dp[j]=max(dp[j],dp[j-v[i+note]]+c[i+note]);
            out=max(dp[j],out);
        }
    }
    cout<<C-out;
    return 0;
}

但是事實(shí)上，這樣的話我們會(huì)發(fā)現(xiàn)dp的時(shí)間復(fù)雜度過高，在第28組數(shù)據(jù)會(huì)導(dǎo)致超時(shí)。因此我們舍去轉(zhuǎn)化的過程，直接求一個(gè)至少裝至n的背包所負(fù)載的最小價(jià)值就可以了

#include<bits/stdc++.h>
#define maxn 5005
using namespace std;
inline char get(){
    static char buf[300000],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,300000,stdin),p1==p2)?EOF:*p1++; 
}
inline long long read(){
    register char c=get();register long long f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
long long n;
long long t[maxn],c[maxn];
//?????????? 
long long V;
long long dp[4005];
int main(){
    //freopen("1.txt","r",stdin);
    n=read();
    long long out=1e18+1;
    for(register long long i=1;i<=n;i++)t[i]=read(),c[i]=read(),t[i]+=1,V=max(V,t[i]);
    V+=n;
    for(register int i=1;i<=V;i++)dp[i]=1e18+1;
    dp[0]=0;
    for(register int i=1;i<=n;i++){
        for(register int j=V;j>=t[i];j--){
            dp[j]=min(dp[j],dp[j-t[i]]+c[i]);
            if(j>=n)out=min(dp[j],out);
            //cout<<dp[j]<<endl;
        }
    }
    cout<<out;
    return 0;
}