85 条题解
-
3
川建国小号 LV 6 @ 2020-08-29 11:19:45
01背包变例
#include<bits/stdc++.h>
using namespace std;
int w[10001],v[10001],a[40003],n,m,p=-1,c;
int main(){
cin>>n>>m>>c;
for(int i=1;i<=m;i++){
cin>>v[i]>>w[i];
}
for(int i=1;i<=m;i++){
for(int j=c;j>=w[i];j--){
a[j]=max(a[j],a[j-w[i]]+v[i]);
}}
for(int i=1;i<=c;i++){
if(a[i]>=n&&p<c-i)p=c-i;
}
if(p==-1)cout<<"Impossible";
else cout<<p;
return 0;
} -
2
普及难度
#include<iostream> #include<cstdio> using namespace std; int dp[10005]; int main(){ int v,n,c,i,k,m,j,cmax=-1; scanf("%d%d%d",&v,&n,&c); for(i=1;i<=n;i++){ scanf("%d%d",&k,&m); for(j=c;j>=m;j--)dp[j]=max(dp[j],dp[j-m]+k); } for(j=0;j<=c;j++)if(dp[j]>=v)cmax=max(cmax,c-j); dp[c]<v?printf("Impossible"):printf("%d",cmax); return 0; } -
1
最开始以为是对V做DP，后来想想，好像填超过V也算填平啊。
之后改为对C做DP求耗费C时能填最大的V是多少，然后贪心找第一个能超过海容量的C。#include <iostream> using namespace std; int mv,n,mc; int dp[100000]={0}; int main() { cin>>mv>>n>>mc; int i,v,c; while(n>0) { n--; cin>>v>>c; for(i=mc;i>=c;i--) { dp[i]=max(dp[i],dp[i-c]+v); } } for(i=0;i<=mc;i++) { if(dp[i]>=mv) { cout<<mc-i<<endl; return 0; } } cout<<"Impossible"<<endl; return 0; } -
1
jerryzheng2005 LV 10 @ 2017-04-17 20:34:48
//p1625 #include<iostream> using namespace std; int v,n,c,q[10001],p[10001],f[10001]; int main() { int i,j; cin>>v>>n>>c; for (i=1;i<=n;i++) cin>>q[i]>>p[i]; for (i=1;i<=n;i++) for (j=c;j>=p[i];j--) f[j]=f[j-p[i]]+q[i]>f[j]?f[j-p[i]]+q[i]:f[j]; for (j=0;j<=c;j++) if (f[j]>=v) { cout<<c-j<<endl; return 0; } cout<<"Impossible"<<endl; return 0; } -
0
/*
/
#define method_1
#ifdef method_1
//
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10000+5;
const int maxc=10000+5;
const int INF=0x3f3f3f3f;
//f[j]表示背包已用容量为j的最大体积
int V,n,C;
int v[maxn],c[maxn];
int f[maxc];
void dp(){
for(int i=1;i<=n;i++){
for(int j=C;j>=c[i];j--){
f[j]=max(f[j],f[j-c[i]]+v[i]);
}
}
for(int i=0;i<=C;i++){
if(f[i]>=V){
printf("%d",C-i);
return;
}
}
printf("Impossible");
}
int main() {
// ios::sync_with_stdio(false);
//freopen("精卫填海.in","r",stdin);
scanf("%d%d%d",&V,&n,&C);
for(int i=1;i<=n;i++){
scanf("%d%d",&v[i],&c[i]);
}
dp();
return 0;
}
#endif
#ifdef method_2
/*/
#endif
#ifdef method_3
/**/
#endif
-
0
心酸 突然发现超过v也可:(
#include <iostream> using namespace std; int k[10000],m[100000]; int dp[10000]; int main(void){ int v,n,c; cin>>v>>n>>c; for(int i=0;i<n;i++){ cin>>k[i]>>m[i]; } for(int i=0;i<n;i++){ for(int j=v;j>=m[i];j--){ dp[j]=max(dp[j],dp[j-m[i]]+k[i]); } } for(int i=0;i<=c;i++){ if(dp[i]>=v) { cout << c - i<<endl; exit(0); } } cout<<"Impossible"<<endl; } -
0
Sky1231 (sky1231) LV 10 @ 2017-06-09 16:06:30
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <limits> #include <string> #include <vector> #include <deque> using namespace std; int n,m,c; vector<int> v; vector<int> w; vector<int> f; void c_v_1() { v.resize(0); w.resize(0); f.resize(0); } int main() { while (~scanf("%d%d%d",&m,&n,&c)) { bool b=0; c_v_1(); v.resize(n+1,0); w.resize(n+1,0); f.resize(c+1,0); for (int i=1;i<=n;i++) { scanf("%d%d",&v[i],&w[i]); for (int j=c;j>=w[i];j--) f[j]=max(f[j],f[j-w[i]]+v[i]); } for (int i=0;i<=c;i++) if (f[i]>=m) { printf("%d\n",c-i); b=1; break; } if (b==0) printf("Impossible\n"); } }-
for (int i=0;i<=c;i++) if (f[i]>=m) { printf("%d\n",c-i); b=1; break;//都怪你 }
-
-
0
Ancell Machine LV 6 @ 2017-05-20 20:35:05
这道题是一个比较普通的01背包
如果f【m】还是小于要填的体积的话直接Impossible
否则从1到m开始扫数组，因为f数组表示的是在还有体力i下能填的最大体积
所以如果遇到一个f【i】>=要填的体积就直接输出体力m-i
#include<iostream>
#include<cstdio>
#include<cctype>
template <typename T>
T read(){
T num=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
num=num*10+ch-'0';
ch=getchar();
}
return num*f;
}
#define read() read<long long>()int w[20000];
int c[20000];
int f[20000];
int main()
{
int q=read(),n=read(),m=read();
for(int i=1;i<=n;++i){
c[i]=read();
w[i]=read();
}
for(int i=1;i<=n;++i)
for(int v=m;v>=w[i];--v)
if(f[v]<f[v-w[i]]+c[i]) f[v]=f[v-w[i]]+c[i];
if(f[m]<q){
printf("Impossible");
return 0;
}
else
for(int i=1;i<=m;++i)
if(f[i]>=q){
printf("%d",m-i);
return 0;
}
return 0;
} -
0
#include<bits/stdc++.h>
#define ll long long
#define st string
using namespace std;
struct he{
int a,b;
}a[10005];
int f[10005];
int main()
{
int v,n,c;
cin>>v>>n>>c;
for(int i=0;i<=n;i++) f[i]=1;
for(int i=1;i<=n;i++) cin>>a[i].a>>a[i].b;
for(int i=1;i<=n;i++){
for(int j=c;j>=a[i].b;j--) if(j-a[i].b>=0) {
f[j]=max(f[j],f[j-a[i].b]+a[i].a);
}
}
for(int i=0;i<=c;i++) {
if(f[i]>=v) {
cout<<c-i<<endl;
return 0;
}
}
cout<<"Impossible"<<endl;
return 0;
} -
0
编译通过...
├ 测试数据 01：答案正确... (0ms, 832KB)
├ 测试数据 02：答案正确... (0ms, 832KB)
├ 测试数据 03：答案正确... (139ms, 832KB)
├ 测试数据 04：答案正确... (27ms, 832KB)
├ 测试数据 05：答案正确... (124ms, 832KB)
├ 测试数据 06：答案正确... (153ms, 832KB)
├ 测试数据 07：答案正确... (209ms, 832KB)
├ 测试数据 08：答案正确... (152ms, 832KB)
├ 测试数据 09：答案正确... (252ms, 832KB)
├ 测试数据 10：答案正确... (283ms, 832KB)---|---|---|---|---|---|---|---|-
Accepted / 100 / 1344ms / 832KB
0/1背包问题，朴素就可以了 -
0
liujiahuijia LV 8 @ 2012-08-20 09:14:32
我的题意啊，我的AC率啊.....
不是填平吗，石头体积多出来不会伤着我们的脚吗？ -
0
xjcjason123 LV 10 @ 2009-11-07 18:12:27
悲剧啊。。。如此简单的题。。。。WA
-
0
Lemon tree LV 8 @ 2009-11-07 15:51:01
两种方法
第一种-原始背包；时间空间由于本题的特殊性都较大。
#include
#include
#define max(a,b) ( (a)>(b)?(a):(b) )
#define min(a,b) ( (a) -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 56ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 166ms
├ 测试数据 10：答案正确... 197ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：419ms没MS........
{Rp+++++++++++++++++++++++++}
var
v,n,c,i,o,j,p:longint;
a,b:array[1..10000] of longint;
f:array[0..10000] of longint;
begin
readln(v,n,c);
for i:=1 to n do
readln(a[i],b[i]);
for i:=1 to n do
for j:=c downto b[i] do
if f[j] -
0
guori12321 LV 8 @ 2009-11-04 22:17:29
简单的背包。 WA了7次。。。 轻敌了...
注意范围。我刚开始用f表示前i个物品搬体积为j的石头所用的体力。然后发现9个点都差一点，最后一个点只差了1。然后读题解，发现应该在体积大于v的f[n,j](j>v)中找，结果要累加一下石头的体积，结果还是爆了。
后来发现，用f表示前i个物品体力为j时最多能搬多少体积的石头。然后从0到c找一下，有没有大于v的情况，有就输出。
这告诫我们，要注意阶段的划分，注意范围...
最后默哀一下我的AC率...
川建国小号
LV 6
@ 2020-08-29 11:19:45
