评测状态 Accepted
题目 P1025 小飞侠的游园方案
递交时间 2015-10-09 18:17:59
代码语言 Pascal
评测机 VijosEx
消耗时间 15 ms
消耗内存 904 KiB
评测时间 2015-10-09 18:18:01
评测结果
编译成功

Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
Linking foo.exe
16 lines compiled, 0.0 sec , 28176 bytes code, 1628 bytes data
测试数据 #0: Accepted, time = 0 ms, mem = 900 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 900 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 904 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 900 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 900 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 900 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 900 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 900 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 900 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 900 KiB, score = 10
Accepted, time = 15 ms, mem = 904 KiB, score = 100
代码
var n,t,i,j:longint;
w,v:array[1..10000]of longint;
f:array[0..100000]of longint;
function max(x,y:longint):longint;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(n);
readln(t);
fillchar(f,sizeof(f),0);
for i:=1 to n do readln(w[i],v[i]);
for i:=1 to n do
for j:=t downto v[i] do
if f[j]<f[j-v[i]]+w[i] then f[j]:=f[j-v[i]]+w[i];
writeln(f[t]);
end.

我要狂刷我的动态规划！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

#include<iostream>
#include<cstdio>
using namespace std;
int max(const int&a,const int&b)
{
if(a>b)return a;
else{
return b;
}
}
int main()
{
int m,n,i,j,v,w[101],c[1001],f[101][1001];
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++){
scanf("%d%d",&w[i],&c[i]);
}
for(i=1;i<=m;i++){
for(v=n;v>=1;v--){
if(c[i]>v){
f[i][v]=f[i-1][v];
}
else{
f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i]);
}
}
}
printf("%d",f[m][n]);
}

###C++ Code
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1000 + 5;
int n,t,v,w,dp[MAXN]={0};
int main()
{
ios::sync_with_stdio(false);
cin>>n>>t;

for(int i=1;i<=n;i++)
{
cin>>v>>w;
for(int j=t;j>=w;j--)
dp[j]=max( dp[j-w] + v , dp[j] );
}

cout<<dp[t];
return 0;

}

#include<stdio.h>
#include<vector>

#define max(a,b) a>b?a:b;

std::vector<int>d;

int main()
{
int n, C;
int V, W;
int i;
while(scanf("%d%d", &n, &C) == 2) //循环好像没用
{
for(i=0;i<=C;++i)
d.push_back(0);

for(i=0; i<n; ++i)
{
scanf("%d%d", &W, &V);
for(int j=C; j>=V; --j)
d[j] = max(d[j], d[j-V]+W);
}
printf("%d\n", d[C]);
}
return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int N,t;
vector<int>n,m,f;
int i,j;

int main()
{
cin>>N>>t;
for(i=0;i<N;++i)
{
cin>>j;
n.push_back(j);
cin>>j;
m.push_back(j);

}
for(i=0;i<=t;++i)
f.push_back(0);

for(j=0;j<N;++j)
for(i=t;i>=0;--i)
if(i>=m[j])
if(f[i]<f[i-m[j]]+n[j])f[i]=f[i-m[j]]+n[j];
cout<<f[t];
return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
const int N=10005;
typedef long long ll;
#define Max(a,b) (a>b)?a:b
int n,W;
ll dp[N][N];
ll v[N];
ll w[N];
int main()
{
cin>>n>>W;
for(int i=0;i<n;i++)
{
int de;
cin>>v[i]>>w[i];
}
for(int i=0;i<n;i++)
for(int j=0;j<=W;j++)
if(j<w[i])
dp[i+1][j]=dp[i][j];
else
dp[i+1][j]=Max(dp[i][j],dp[i][j-w[i]]+v[i]);
cout<<dp[n][W];

return 0;
}
哪位大神指教一下，哪错了？

/*************************************************************************
> File Name: pack_2.c
> Author: Netcan
> Mail: 1469709759@qq.com
> Created Time: 2015/3/7 16:31:02
************************************************************************/

#include<stdio.h>
#include<string.h>

#define max(a,b) a>b?a:b;

int main()
{
int n, C;
int V, W;
static int d[1000];
while(scanf("%d%d", &n, &C) == 2) {
memset(d, 0, sizeof(d)/sizeof(int));

for(int i=0; i<n; ++i) {
scanf("%d%d", &W, &V);
for(int j=C; j>=V; --j)
d[j] = max(d[j], d[j-V]+W);
}
printf("%d\n", d[C]);
}
return 0;
}

/*************************************************************************
> File Name: pack_2.c
> Author: Netcan
> Mail: 1469709759@qq.com
> Created Time: 2015/3/7 16:31:02
************************************************************************/

#include<stdio.h>
#include<string.h>

#define max(a,b) a>b?a:b;

int main()
{
int n, C;
int V, W;
static int d[1000];
while(scanf("%d%d", &n, &C) == 2) {
memset(d, 0, sizeof(d)/sizeof(int));

for(int i=0; i<n; ++i) {
scanf("%d%d", &W, &V);
for(int j=C; j>=V; --j)
d[j] = max(d[j], d[j-V]+W);
}
printf("%d\n", d[C]);
}
return 0;
}

/*************************************************************************
> File Name: 1025.c
> Author: Netcan
> Mail: 1469709759@qq.com
> Created Time: 2015/3/7 15:41:02
************************************************************************/

#include<stdio.h>
inline int max(int a, int b) {
return a>b?a:b;
}

int main()
{
int N, T;
static int f[105], t[105];
static int d[105][1005];
while(scanf("%d%d", &N, &T) == 2) {
for(int i=0; i<N; ++i)
scanf("%d%d", &f[i], &t[i]);
for(int i=0; i<=N; ++i)
for(int j=0; j<=T; ++j) {
d[i][j] = i==0?0:d[i-1][j];
if(i>0 && j>=t[i-1]) d[i][j] = max(d[i-1][j], d[i-1][j-t[i-1]]+f[i-1]);
}
printf("%d\n", d[N][T]);
}

return 0;
}

/*************************************************************************
> File Name: 1025.c
> Author: Netcan
> Mail: 1469709759@qq.com
> Created Time: 2015/3/7 15:41:02
************************************************************************/

#include<stdio.h>
inline int max(int a, int b) {
return a>b?a:b;
}

int main()
{
int N, T;
static int f[105], t[105];
static int d[105][1005];
while(scanf("%d%d", &N, &T) == 2) {
for(int i=0; i<N; ++i)
scanf("%d%d", &f[i], &t[i]);
for(int i=0; i<=N; ++i)
for(int j=0; j<=T; ++j) {
d[i][j] = i==0?0:d[i-1][j];
if(i>0 && j>=t[i-1]) d[i][j] = max(d[i-1][j], d[i-1][j-t[i-1]]+f[i-1]);
}
printf("%d\n", d[N][T]);
}

return 0;
}

#include<stdio.h>

#define max 100
#define maxweight 1000

int Max(int x,int y);
int main()
{
int i,j,volume,n;
int w[max+10],v[max+10];
int m[max+10][maxweight+10];

scanf("%d",&n);
scanf("%d",&volume);
for(i = 1;i <= n; i++)
{
scanf("%d",&v[i]);
scanf("%d",&w[i]);
}

for(j = w[n];j <= volume; j++)
m[n][j]=v[n];
for(j = 0;j < w[n]; j++)
m[n][j]=0;

for(i = n-1;i >= 1; i--)
{
for(j = volume;j >= 1; j--)
{
if(j >= w[i])
{
m[i][j]=(m[i+1][j]>m[i+1][j-w[i]]+v[i])?m[i+1][j]:m[i+1][j-w[i]]+v[i];
}
else if(j < w[i])
m[i][j]=m[i+1][j];
}
}
printf("%d",m[1][volume]);
return 0;
}

int Max(int x,int y)
{
if(x>=y)
return x;
else
return y;
}

简单背包：滚动数组：空间优化，我忘了空间优化；但是这样可读性更强。
动规的优化：1003 过河状态压缩 与此题一样都可以进行空间优化。
#include<iostream>
using namespace std;
int a[1003][103];
int time[103], like[103];
int size, t;
void go(){
int i, j;
for (i = 0; i < size; i++)a[0][i] = 0;
for (i = 0; i < t; i++) a[i][size] = 0;
for (j = size - 1; j >= 0; j--){
for (i = 1; i <= t; i++){
a[i][j] = 0;
if (i >= time[j]){
a[i][j] = like[j] + a[i - time[j]][j + 1];
}
if (a[i][j] < a[i][j + 1])
a[i][j] = a[i][j + 1];
}
}
cout << a[t][0] << endl;
}
int main(){
//freopen("in.txt", "r", stdin);
cin >> size >> t;
int i;
for (i = 0; i < size; i++)cin >> like[i] >> time[i];
go();
return 0;
}

01背包的解题公式，见到这种题直接复制就行了，因为顺序搞反了，我的AC率！！

#include<iostream>
using namespace std;
int w[2000],c[2000];
int f[2000];
int main()
{
int m,n;
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>c[i]>>w[i];
for(int i=1;i<=n;++i)
for(int v=m;v>=w[i];v--)
if(f[v-w[i]]+c[i]>f[v])
f[v]=f[v-w[i]]+c[i];
cout<<f[m];
return 0;
}

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 744 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 744 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 748 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 748 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 748 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 748 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 744 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 748 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 748 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 748 KiB, score = 10
Accepted, time = 15 ms, mem = 748 KiB, score = 100
想当初，洒家费了多大劲，还死得那么惨，今日总算AC了！

我擦，把我的采药这道题的AC程序直接复制过来，然后换下读入顺序，因为他是先读价值再读容量，妈呀，直接AC了居然！

block code

program P1104;
uses math;
var t,m,i,a,b,ans,j:longint;
data:array[0..1000] of longint;
begin
read(m,t); ans:=0; fillchar(data,sizeof(data),0);
for i:=1 to m do
begin
read(b);read(a);
for j:=t downto a do
begin
data[j]:=max(data[j],data[j-a]+b);
end;
end;

write(data[t]);
end.

#include<cstdio>
using namespace std;
int n,t,v[101],w[101],f[1001],i,j;
int main()
{

scanf("%d%d",&n,&t);
for(i = 1 ; i <= n ; i ++)
scanf("%d%d",&w[i],&v[i]);
for(i = 1 ; i <= n ; i ++)
for(j = t ; j >= 1 ; j --)
if(f[j]>f[j-v[i]]+w[i]||j-v[i]<0);
else f[j]=f[j-v[i]]+w[i];
printf("%d",f[t]);
}

#include<cstdio>
#include<algorithm>
using namespace std;
#define IOFileName "P1025"
const int maxt=1002;
int n,t,fi,ti;
int T[maxt]={0};
int main(){
//freopen(IOFileName".in","r",stdin);
//freopen(IOFileName".out","w",stdout);
scanf("%d\n%d\n",&n,&t);
for(int i=0;i<n;i++){
scanf("%d %d\n",&fi,&ti);
for(int j=t;j>=0;j--){
if((T[j]&&j+ti<=t)||j==0){
T[j+ti]=max(T[j+ti],T[j]+fi);
}
}
}
printf("%d\n",*max_element(T,T+t+1));
}
252MB+15MS

3次WA...

跪求啊

我基础烂，新手一枚，为了比赛，有人教我错在哪儿吗？？谢谢。
read(n,m);
for i:=1 to n do
begin
readln(t1[i],t2[i]);
end;
for i:=1 to n do
begin
t3[i]:=t2[i]/t1[i];
end;
repeat
for i:=1 to n do
begin
if t3[i]<t3[i+1] then h:=t3[i]; t3[i]:=t3[i+1]; t3[i+1]:=h;
h:=t2[i]; t2[i]:=t2[i+1]; t2[i+1]:=h;
h:=t1[i]; t1[i]:=t1[i+1]; t1[i+1]:=h;
end;
until t2[i]>=t2[i+1];
for i:=1 to n do
begin
if (m>=t1[i]) then y:=y+t2[i]; m:=m-t1[i];
end;
write(y:0:0);
end.