/**
可能真的是状态不好
这个题都改疯了
一开始算钱算错了
然后少考虑了情况
然后背包写错了……………………
**/
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define maxn (100003 + 5)
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
typedef long long int LLI;

struct node {
    int p1;
    int p2;
} op[maxn];

bool cmp(node a,node b) {
    return (a.p2 - a.p1) > (b.p2 - b.p1);
}

int dp[maxn],l = 0;

int packbag(int p,int q) {
    int  minx = -1;
    memset(dp,-1,sizeof(dp));
    dp[0] = 0;
    for(int i = 0; i < l; i ++) {
        for(int j = p; j >= 0; j --) {
            if(dp[j] == -1) continue;
            int x = j + op[i].p1;
            x = min(x,p);
            if(dp[x] == -1) dp[x] = dp[j] + op[i].p2 - op[i].p1 - q;
            else            dp[x] = min(dp[x],dp[j] + op[i].p2 - op[i].p1 - q);
            if(x >= p) {
                if(minx == -1)  minx = dp[x];
                else            minx = min(dp[x],minx);
            }
        }
    }
    return minx;
}


int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int n,p,sum = 0,sum2 = 0;
    scanf("%d%d",&n,&p);
    getchar();
    for(int i = 1; i <= n; i ++) {
        char str[maxn];
        gets(str);
        int x = 0,j = 0;
        while(str[j] == ' ')    j ++;
        while(isalnum(str[j])) {
            x = x * 10 + str[j] - '0';
            j ++;
        }
        while(str[j] == ' ')   j ++;
        if(str[j] == '\0') {
            sum += x;
        } else {
            int y = 0;
            while(isalnum(str[j])) {
                y = y * 10 + str[j] - '0';
                j ++;
            }
            if(y <= p + x)  sum += x;
            else {
                op[l].p1 = x;
                op[l ++].p2 = y;
            }
        }
    }
    sort(op,op + l,cmp);
    for(int i = 0; i < l; i ++)   sum2 += (op[i].p2 - p);
    int fa = sum;
    for(int i = 0; i < l; i ++)   fa += op[i].p1;
    if(sum >= p)    printf("%d\n",sum2 + sum);
    else {
        int temp = packbag(p - sum,p);
        if(temp == -1)  printf("%d\n",fa);
        else {
            sum2 = sum2 + sum - temp;
            printf("%d\n",sum2);
        }
    }
    return 0;
}

最小背包啊。。。。坑了好久~~
处理完普通物品和不要的魔法物品 有现金a
如果现金可以购买卷轴的话 就直接弄得魔法物品得到到答案
否则 先讨论是否当垃圾卖完可以买到卷轴 不可以的话直接当废品卖了。
否则的话，还差res=p-a....
将魔法卷轴处理一下，a:=当普通卖的价格，b:=用卷轴之后的增益。
答案就是：现金+∑普通卖的价格+∑用卷轴之后额外的增益-∑为了买卷轴舍弃的最小的增益
最小背包~~~一开始我也以为是贪心~~~

我贴一个可以看的懂的程序

var

s,sum,temp,n,pi,i,j:longint;

a,b:array[0..1001]of longint;

f:array[0..15001] of longint;

function min(a,b:longint):longint;

begin

if a>b then exit(b);

exit(a);

end;

procedure easyway;

begin

sum:=0;

for i:=1 to n do

if b[i]-1 then inc(sum,a[i]+b[i])

else inc(sum,a[i]);

writeln(sum);

halt;

end;

begin

readln(n,pi);

fillchar(b,sizeof(b),$ff);

for i:=1 to n do

begin

read(a[i]);

inc(s,a[i]);

if not eoln then

begin

read(b[i]);

dec(b[i],pi+a[i]);

if b[i]pi then f[pi]:=min(f[pi],f[i-a[j]]+b[j])

else f[i]:=min(f[i],f[i-a[j]]+b[j])

end;

writeln(sum-f[pi]);

end.

感动- -,原来是背包,,以为贪心,然后- -...

秒杀

留名~~

just so-so,楼下的题解都好正啊！！我就不献丑了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

无语...一开始沙茶了 用贪心......

贪心+01背包. 01背包用一维的就好了 不用滚动数组

var i,j,l,k,kk,ss,sum,sum1,sum2,now,money2,pp,n,p,money:longint;

st:string;

b:boolean;

m1,m2,less:array[0..10001]of longint;

f:array[0..10001]of longint;

function min(a,b:longint):longint;

begin

if a>b then min:=b else min:=a;

end;

begin

readln(n,p);

j:=0;

money:=0;

for ss:=1 to n do begin

sum1:=0; sum2:=0;

read(sum1);

while not eoln do read(sum2);

readln;

if sum2=0 then inc(money,sum1)

else begin

if sum1+p>=sum2 then inc(money,sum1)

else begin

inc(j);

m1[j]:=sum1;

m2[j]:=sum2;

end;

end;

end;

n:=j;

money2:=money;

for i:=1 to n do inc(money2,m1[i]);

if money2=p then begin

for i:=1 to n do inc(money,m2[i]-p);

writeln(money);

halt;

end

else begin

for i:=1 to n do less[i]:=m2[i]-m1[i]-p;

now:=0;

money2:=money;

for i:=1 to n do inc(money2,m1[i]);

for j:=0 to 10001 do f[j]:=87654321;

f[money]:=0;

for i:=1 to n do

for j:=10001 downto money do begin

if (j>m1[i])and(f[j-m1[i]]87654321) then f[j]:=min(f[j],f[j-m1[i]]+less[i]);

if (j>p)and(f[j]

楼下详细+正解.......放心做吧..囧..

Accepted 有效得分：100 有效耗时：0ms

悲剧了,早上匆匆写完就去上物理课了，然后发现80分……仔细回想一下，原来很弱智的一个方面都没考虑到……中午稍微加上几句话，AC……

提示一下思路：

看清楚题意之后，很容易就想到了贪心：

1)普通物品直接卖掉

2)鉴定前价值+鉴定卷轴价值>=鉴定后价值,也直接卖掉

这两个方面可以直接在输入时处理,记录一共卖掉的价值ans,至于剩下的物品，我们用两个数组a和b分别记录这个物品鉴定前的价值和鉴定后能多得到的价值

还有一点最重要的贪心:

3)我们只需要拥有一张鉴定卷轴就够了！因为这个可以循环利用！但是，我们必须要有买一张的钱……

接下来又可以有贪心：

4)如果输入时卖掉的物品已经积累了p的价值，直接买卷轴，不断卖出剩下的物品(到没有物品时，自然就不要再买了……)

5)如果全部物品都直接卖掉积累起来的价值还

哈哈~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

build

先贪心后DP、、只要能买到一张鉴定的卷轴就可以了、

刚开始凹了一把、、少了个判断、、全错了、、诶、、

LX在装逼、、-0-、、

我也不知道

这个题是怎么回事……