传送门——P2370 yyy2015c01 的 U 盘
题解：题目意思很好理解，就是说，当能够达到预期的U盘的最小接口（接口越大，能传递的文件越大），然后我们就需要先看题目了，有n个文件，每个文件有其自己的重量和价值，我们的U盘最多就只能装S大小的文件，因此我们很容易就想到了01背包，但是和01背包不同的地方就我们会有一个对文件重量的限制，不允许超过L，那我们该如何去得到这个最小的L呢，我们不难想到二分答案，我们对文件的大小进行排序，然后二分，如果算出来的价值小了，就向右取，如果价值大于预期，就向左取，然后循环往复，用ans去记录能够达到预期的的最小的接口大小L
注意：每次进行二分操作的时候都要重新初始化dp数组，还有就是在进行01背包的时候需要对文件的大小进行筛选，大于接口大小的都要去跳过
//二分答案枚举文件大小，价值就将接口减小，小于价值就将接口增大
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,p,s;
struct node
{
int w;
int v;
}a[1005];
int dp[1005];//表示大小为j内存的u盘能保留的最大价值
int L;//限制传送的最大文件
int ans;//用来记录可行的数值
bool cmp(node a,node b)
{
return a.w<b.w;
}
signed main()
{
cin>>n>>p>>s;
for(int i=1;i<=n;i++)
{
cin>>a[i].w>>a[i].v;
}
sort(a+1,a+1+n,cmp);
int l=1,r=n;
int mid=0;
int flag=0;
while(l<=r)
{
memset(dp,0,sizeof(dp));
mid=(l+r)>>1;
L=a[mid].w;
for(int i=1;i<=n;i++)
{
if(a[i].w>L)
continue;
for(int j=s;j>=a[i].w;j--)
{
dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
}
}
if(dp[s]>=p)
{
ans=L;
r=mid-1;
flag=1;
}
else
{
l=mid+1;
}
}
if(flag==0)
{
cout<<"No Solution!";
return 0;
}
cout<<ans;
return 0;
} 传送门——Checkout Assistant
题解：这题一位大佬写的巨妙，一开始完全没想到，我以为是去找出对应时间所能获得的最大价值，然后和剩下的时间去做比较，这部分的物品的个数小于剩余部分的时间，那么这部分就是应该是我所获得的最小花费 ，但并不是我这样想的真正的做法应该将时间去当做重量，花费当做价值，背包的最大容量就应该为最大的时间加上n个物品的时间，因为最大时间的物品有可能其扫描时间有可能会大于所有物品个数
我们可以知道，在扫描时间ti里面，我么可以获得的物品为ti+1个物品，然花费vi，然后背包容量为max（t[i]）+n；我们可以将这个问题转换为求获得至少k个物品的最小花费为dp[j]；
然后注意开long long就可以快速的过掉这个题了，真实难度没有蓝题水平，但是其中的思维确实要想清楚
//Checkout Assistant
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int t[2005];
int v[2005];
int dp[4005];
signed main()
{
cin>>n;
int maxn=0;
for(int i=1;i<=n;i++)
{
cin>>t[i]>>v[i];
t[i]++;
maxn=max(maxn,t[i]);
}
int ans=maxn+n;
memset(dp,0x3f3f3f3f,sizeof(dp));dp[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=ans;j>=t[i];j--)
{
dp[j]=min(dp[j],dp[j-t[i]]+v[i]);
}
}
int sum=0x3f3f3f3f3f3f3f3f;
for(int i=n;i<=ans;i++)
{
sum=min(sum,dp[i]);
}
cout<<sum;
return 0;
}
