題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)初始值point，然后給出一個(gè)minute表示每分鐘減少的分?jǐn)?shù)和time表示做完該題需要的分?jǐn)?shù)，請(qǐng)給出一個(gè)合適的做題順序要求在規(guī)定時(shí)間內(nèi)最后得到的分?jǐn)?shù)最高

題目分析：我們可以把時(shí)間看做背包，將分?jǐn)?shù)看做物品，這樣就轉(zhuǎn)換成了一個(gè)簡(jiǎn)單的01背包問(wèn)題，主要是我們應(yīng)該給選擇的物品來(lái)一個(gè)次序，每個(gè)題目因?yàn)闀r(shí)間原因，所得到的分?jǐn)?shù)是不同的，導(dǎo)致每個(gè)題目都有一個(gè)優(yōu)先級(jí)，我們接下來(lái)討論一下該怎么排序。

首先，我們要選擇在性價(jià)比最優(yōu)的情況下排序，因?yàn)槊總€(gè)題目的分?jǐn)?shù)涉及到了做題時(shí)間，每個(gè)題目的最終分值我們可以表示為：

score=point-minute*(k+time);? (k表示的是之前已經(jīng)經(jīng)歷過(guò)的時(shí)間)

那么我們?cè)诒容^兩兩題目的性價(jià)比時(shí)，只需要假設(shè)前一個(gè)題目是第一個(gè)開始做的，這樣k就等于0了，

所以我們可以得出這樣的一個(gè)比較式：

bool cmp(const Node& a,const Node& b)

{

? ? ? ? return a.point-a.minute*a.time+b.point-b.minute*(a.time+b.time)>

b.point-b.minute*b.time+a.point-a.minute*(a.time+b.time);

}

當(dāng)然，化簡(jiǎn)一下，可以變成這樣：

?bool cmp(const Node& a,const Node& b)

{

? ? ? ? return a.minute*a.time+b.minute*(a.time+b.time)>b.minute*b.time+a.minute*(a.time+b.time);

}

這樣我們就處理完了最難得一步了，接下來(lái)就是簡(jiǎn)單的01背包問(wèn)題了，需要注意的是每個(gè)變量都要記得開longlong，因?yàn)樯婕暗搅顺朔▎?wèn)題，有的式子如果不轉(zhuǎn)換成longlong運(yùn)算的話會(huì)爆掉int，丟失精度。

直接上代碼了：

#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=60;LL dp[100000+100];struct Node {LL point,minute,time;friend bool operator<(const Node& a,const Node& b){return a.time*a.minute+(a.time+b.time)*b.minute<b.time*b.minute+(b.time+a.time)*a.minute;} }a[N];int main() {int n,t;while(scanf("%d%d",&n,&t)!=EOF){memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i].point,&a[i].minute,&a[i].time);sort(a+1,a+1+n);LL ans=0;for(int i=1;i<=n;i++)for(int j=t;j>=a[i].time;j--){dp[j]=max(dp[j],dp[j-a[i].time]+a[i].point-a[i].minute*j);ans=max(ans,dp[j]);}printf("%lld\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的qduoj - 今晚一起打CF吧——Codeforces，十三亿人的ACM梦。(排序背包)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。