作業

jzoj 1986

解題思路：

‘光光’在暑假有很多作業，但他不能全部做完，他只有一定的時間，某一項作業沒做完（有一點沒做完也算），他就會有一個不開心值，現在問不開心值最小是多少

輸入樣例

5 3 2 6 1 3 4 7

輸出樣例

6

數據范圍

100%的數據中， k<=100000， ti<=10000， pi<=10000；
30%的數據中， n<=20；
100%的數據中， n<=500。

解題思路：

我們可以先算出最大不開心值，然后用01背包算出最多可以消去多少不開心值，然后相減得出結果

代碼：

#include<cstdio> #define max(x,y) (x)>(y)?(x):(y) using namespace std; int k,n,t,s,num,f[100500]; int main() {scanf("%d %d",&k,&n);for (int i=1;i<=n;++i){scanf("%d %d",&t,&s);num+=s;//不開心總值for (int j=k;j>=t;--j)//01背包f[j]=max(f[j],f[j-t]+s);//可消去的最大的不開心值}printf("%d",num-f[k]);//相減return 0; }

總結

以上是生活随笔為你收集整理的【背包】作业（jzoj 1986）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。