一、畅爽的甩卖
【问题描述】
MrKill 出国买回来了一大堆东西,看着就烦,真烦。
正在回国途中,他突然接到通知,不能够很多海外物品,这可是一个大好的理由来
搪塞他的朋友,这一堆东西都可以卖给海外黄牛赚差价。清点了一下,一共有 n 个物品,
每个物品有 wi 的重量,pi 的价值,但是他的行李箱只有 m 的承重,也就是说,他只
能拿一部分物品出来售卖,当然他想得到最多的钱,那样就可以买最多的游戏了。
MrKill 看着这一堆即将变成 steam 钱包的商品:
“嗨,真香”。
【输入格式】
输入文件名为 sell.in。
输入数据第一行为 n,m 接下来 n 行分别为 wi 和 pi
【输出格式】
输入文件名为 sell.out。
一个整数,表示最大价值
【输入输出样例 1】
sell.in sell.out
2 2 3
1 3
2 2
4 3 10
3 10
2 7
2 8
1 1
样例 1 解释:只拿第一个商品最优
样例 2 解释:只拿第一个商品最优
【数据规模与约定】
对于 20%的数据 n ≤ 20 ,
另有 20%的数据 n ≤ 10^5 , 1 ≤ wi ≤ 2
另有 20%的数据 n ≤ 5*10^2 , 1 ≤ pi ≤ 20 ;
对于 100%的数据 n ≤ 10^5,m ≤ 3*10^5 , 1 ≤ wi ≤ 3 , 1≤ pi ≤ 10^10
因为wi的特殊性，这题的思路是dp，我们考虑到把三种重量的物品分开来考虑，那么有后效性的就是每种商品在花费了多少重量上已经用了几个。
于是我们很容易想到把每种商品按价值排序之后就可以进行dp了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define il inline
#define db double
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
il int gi()
{
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
y=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*y;
}
il ll gl()
{
ll x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
y=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*y;
}
struct thing
{
ll p;
int w;
}t1[100045],t2[100045],t3[100045];
il bool cmp(thing a,thing b)
{
return a.p>b.p;
}
ll f[300045][4];
int main()
{
int n=gi(),m=gi(),wei;
int w1=0,w2=0,w3=0;
for(int i=1;i<=n;i++)
{
wei=gi();
if(wei==1)
{
t1[++w1].w=wei;
t1[w1].p=gl();
}
if(wei==2)
{
t2[++w2].w=wei;
t2[w2].p=gl();
}
if(wei==3)
{
t3[++w3].w=wei;
t3[w3].p=gl();
}
}
sort(t1+1,t1+1+w1,cmp);
sort(t2+1,t2+1+w2,cmp);
sort(t3+1,t3+1+w3,cmp);
for(int i=1;i<=m;i++)
{
if(f[i-1][0]+t1[f[i-1][1]+1].p>=f[i][0])
{
f[i][0]=f[i-1][0]+t1[f[i-1][1]+1].p;
f[i][1]=f[i-1][1]+1;
f[i][2]=f[i-1][2];
f[i][3]=f[i-1][3];
}
if(f[i-2][0]+t2[f[i-2][2]+1].p>=f[i][0]&&i>1)
{
f[i][0]=f[i-2][0]+t2[f[i-2][2]+1].p;
f[i][1]=f[i-2][1];
f[i][2]=f[i-2][2]+1;
f[i][3]=f[i-2][3];
}
if(f[i-3][0]+t3[f[i-3][3]+1].p>=f[i][0]&&i>2)
{
f[i][0]=f[i-3][0]+t3[f[i-3][3]+1].p;
f[i][1]=f[i-3][1];
f[i][2]=f[i-3][2];
f[i][3]=f[i-3][3]+1;
}
}
printf("%lld
",f[m][0]);
return 0;
}