题解 - Vijos

3

2472207427@qq.com LV 8 @ 7 年前

样例过了的提交却全错的同学看：

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cctype>
#include<algorithm>
using namespace std;
int n,t,tt[11000],h[10000],f[10000];
int main()
{
    cin>>n;
    cin>>t;
    for(int i=1;i<=n;i++)
        cin>>h[i]>>tt[i];
    for(int i=1;i<=n;i++)
    for(int j=t;j>=tt[i];j--)
    f[j]=max(f[j],f[j-tt[i]]+h[i]);
    cout<<f[t];
    return 0;
}

你们是不是把输入顺序搞反了？

先输入高兴值后输入耗费时间

1

川建国小号 LV 6 @ 4 年前

#include<bits/stdc++.h>
using namespace std;
int w[10001],v[10001],a[80003],n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++){
for(int j=m;j>=w[i];j--){
a[j]=max(a[j],a[j-w[i]]+v[i]);
}
}
cout<<a[m];
return 0;
}
求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞
求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞
求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞
求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞
求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞
求赞求赞求赞求赞求赞求赞求赞求赞求赞
求赞求赞求赞求赞求赞求赞求赞求赞
求赞求赞求赞求赞求赞求赞求赞
求赞求赞求赞求赞求赞求赞
求赞求赞求赞求赞求赞
求赞求赞求赞求赞

1

s_y_k_ LV 7 @ 5 年前

这是0/1背包问题，每个娱乐项目要么选要么不选，算作动态规划的入门吧。

// 1025.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>
using namespace std;
int like[1010] = { 0 }, cost[1010] = { 0 }, f[1010] = { 0 };
int main()
{
    int N, t;
    cin >> N >> t;
    for (int i = 0; i < N; i++)
        cin >> like[i] >> cost[i];
    for (int i = 0; i < N; i++)
    {
        for (int j = t; j >= cost[i]; j--)
            f[j] = max(f[j], f[j - cost[i]] + like[i]);
        /*
        从最大时间开始，直到时间等于当前项目的时间。
        当总容量是j的时候，遇到了第i个娱乐项目，那
        么就要比一下：是当前已有情况喜欢程度更高呢
        ，还是把当前时间中的一部分用当前项目来替代
        获得的喜欢程度更高呢？把所有大于当前项目时
        间的f[j]都拿来做上述检查，当遍历完所有项目
        后，最优解就出来了。
        */
    }
    cout << f[t] << endl;
    return 0;
}

1

PowderHan LV 10 @ 8 年前

/*
裸题~很明显的0/1背包问题
因为每个活动要么选择一次要么不选
时间是容量   活动是物品
直接一次0/1背包就能过了
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int f[1005];
int n,T;

int main()
{
    int w,t;
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&w,&t);
        for(int j=T;j>=t;j--)
            f[j]=max(f[j],f[j-t]+w);
    }
    printf("%d\n",f[T]);
    return 0;
}

1

2015031103004 LV 7 @ 9 年前

#include<iostream>
#include<algorithm>
using namespace std;
int n,t,v[1005][1005],t1[1005],p[1005];
int main()
{
cin>>n>>t;
for(int i=1;i<=n;i++)
{
cin>>p[i]>>t1[i];
}
for(int i=0;i<=t;i++)
v[0][i]=0;

for(int i=0;i<=n;i++)
v[i][0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=t;j++)
{
if(j>=t1[i])
v[i][j]=max(v[i-1][j-t1[i]]+p[i],v[i-1][j]);
else
v[i][j]=v[i-1][j];
}
cout<<v[n][t]<<endl;

return 0;
}

0

WC0171 LV 5 @ 9 个月前

明显是一道dp~~（废话）~~
01背包~~难度：4~~
```

#include <iostream>
#include <cstdio>
#define N 105
#define T_ 105
using namespace std;
inline int read()
{
    int r = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
    return r * f;
}
int n, m, f[T_], w[N], v[N];
int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++) v[i] = read(), w[i] = read();
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= w[i]; j--) f[j] = max(f[j], f[j-w[i]] + v[i]);
    cout << f[m];
    return 0;
}

0

Wj (hlbchenweiping) LV 6 @ 4 年前

#inclde <iostream>
using namespace std;
int n,t,f[1001],w[1001],v[1001];
int main()
{
cin>>n>>t;
for(int i=0;i<=n;i++)
cin>>v[i]>>w[i];
for(int i=0;i<=n;i++)
{
for(int j=t;j>=0;j--)
if(j>=w[i])
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
cout<<f[t];
return 0;
}

0

Icewear LV 5 @ 4 年前

01背包
滚动数组

#include <iostream>
#include <cstdio>
using namespace std;
int f[1001]={0};
int n,m;
int a,b;
int main () {
    scanf("%d%d",&n,&m);
    for (int q=1;q<=n;q++) {
        scanf("%d%d",&a,&b);
        for (int w=m;w>=b;w--) {
            f[w]=max(f[w],f[w-b]+a);
        }
    }
    printf("%d\n",f[m]);
    return 0;
}

0

vicar LV 8 @ 5 年前

#include<iostream>
#include<string.h>
using namespace std;
int f[100];
int main(){
int v,w,t,n;
cin>>n>>t;
memset(f,0,sizeof(f));
while(n--){
cin>>v>>w;
for(int i=t;i>=0;i--){
if(i>=w)f[i]=max(f[i-w]+v,f[i]);
}
}
cout<<f[t]<<endl;
}

0

♂YPY♂ LV 4 @ 7 年前

var
f:array[0..1000]of longint;
like,time:array[1..100]of longint;
i,j,n,t:longint;
begin
readln(n);
readln(t);
for i:=1 to n do
readln(like[i],time[i]);
fillchar(f,sizeof(f),0);
for i:=1 to n do
for j:=t downto 1 do
if j-time[i]>=0 then if f[j-time[i]]+like[i]>f[j] then f[j]:=f[j-time[i]]+like[i];
writeln(f[t]);
end.

0

tootal (hzq) LV 9 @ 8 年前

手写了一个暴力dp，无任何优化，结果。。。AC了。。
~~~
#include <iostream>
#include <cstdio>
using namespace std;
int n,t,A[105],T[105],F[105][1005];
int main(){
scanf("%d%d",&n,&t);
for(int i = 1;i <= n;i++) scanf("%d%d",&A[i],&T[i]);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= t;j++)
if(j >= T[i]) F[i][j] = max(F[i - 1][j],F[i - 1][j - T[i]] + A[i]);
else F[i][j] = F[i - 1][j];
printf("%d\n",F[n][t]);
return 0;
}

还是练练优化吧。。。

#include <iostream>
#include <cstdio>
using namespace std;
int n,t,A,T,F[1005];
int main(){
scanf("%d%d",&n,&t);
for(int i = 1;i <= n;i++) {
scanf("%d%d",&A,&T);
for(int j = t;j >= T;j--) F[j] = max(F[j],F[j - T] + A);
}
printf("%d\n",F[t]);
return 0;
}

0

chronix LV 8 @ 8 年前

#include <cstdio>

int max(int a,int b){
return a>b?a:b;
}

int main(){
// freopen("in.txt","r",stdin);
int n,v;
int c[1000],w[1000];
int f[1000]={0};
scanf("%d%d",&n,&v);
for(int i=1;i<=n;i++)
scanf("%d%d",&w[i],&c[i]);
for(int i=1;i<=n;i++)
for(int j=v;j>=c[i];j--)
f[j]=max(f[j],f[j-c[i]]+w[i]);
printf("%d",f[v]);

return 0;
}

0

正在加载...99% LV 8 @ 9 年前

var
a,t:array[1..100]of integer;
f:array[0..100,0..1000]of longint;
mt,n,i,j:integer;
begin
readln(n);
readln(mt);
for i:=1 to n do
readln(a[i],t[i]);
fillchar(f,sizeof(f),0);
for i:=1 to n do
for j:=1 to mt do
begin
f[i,j]:=f[i-1,j];
if (j>=t[i])and(f[i-1,j-t[i]]+a[i]>f[i,j])then
f[i,j]:=f[i-1,j-t[i]]+a[i];
end;
writeln(f[n,mt]);
end.

0

846047746 LV 8 @ 9 年前

#include<cstdio>
int f[1000],n,m,v,p;
int main()
{
scanf("%d%d",&n,&m);
while(n--)
{
scanf("%d%d",&v,&p);
for(int i=m;i>=p;--i)
f[i]=std::max(f[i],f[i-p]+v);
}
printf("%d",f[m]);
return 0;
}

0

随随便便 LV 6 @ 9 年前

记忆化搜索（通俗易通啊）

#include <iostream>

#include <fstream>

using namespace std;

ifstream fin("fin.in");

ofstream fout("fout.out");

int n,t,f[110],h[110],g[1100][110]={0};

void Input()

{

cin>>n>>t;

for(int i=1;i<=n;i++) cin>>f[i]>>h[i];

}
int algorithm(int y,int x)

{

// fout<<y<<" "<<x<<"\n";

if(x==0||y==0) return 0;

if(g[y][x]) return g[y][x];

int a=0,b;

if(y>=h[x]) a=algorithm(y-h[x],x-1)+f[x];

b=algorithm(y,x-1);

if(a>b) b=a;

g[y][x]=b;

return g[y][x];

}

int main()

{

Input(); //输入

// for(int i=1;i<=10;i++)

// for(int j=1;j<=10;j++)

//fout<<g[i][j];

int m=algorithm(t,n); //算法

cout<<m;

}

递推（总算弄懂了，汗）

#include <iostream>

#include <fstream>

using namespace std;

ifstream fin("fin.in");

ofstream fout("fout.out");

int n,t,f[110],g[110],h[1010];

void Input()

{

cin>>n>>t;

for(int i=1;i<=n;i++) cin>>f[i]>>g[i];

}

int main()

{

Input(); //输入

for(int i=1;i<=n;i++){

for(int j=t;j>=g[i];j--)

if(h[j]<h[j-g[i]]+f[i]) h[j]=h[j-g[i]]+f[i];

}
cout<<h[t];

}

0

残阳~·鲜血如虹 LV 7 @ 9 年前

求大神指点

0

残阳~·鲜血如虹 LV 7 @ 9 年前

这哪里错了
var i,j,k,m,n,l,x,y:longint;
a,b:array[0..1000]of longint;
c:array[0..100,0..1000]of longint;
begin
readln(n);
readln(m);
for i:=1 to n do
read(a[i],b[i]);
for i:=1 to n do
begin
for j:=1 to m do
begin
if b[i]>j then
c[i,j]:=c[i-1,j];
if (b[i]=j)and(a[i]>c[i,j]) then
c[i,j]:=a[i];
if (b[i]<j)and(c[i-1,j]>c[i-1,j-b[i]]+a[i]) then
c[i,j]:=c[i-1,j];
if (b[i]<j)and(c[i-1,j]<=c[i-1,j-b[i]]+a[i]) then
c[i,j]:=c[i-1,j-b[i]]+a[i];
end;
end;
write(c[n,m]);
end.

0

约会王 LV 5 @ 9 年前

#include<iostream>
using namespace std;
const int max_place=1000;
const int max_time=1000;
int totaltime;
int totalplace;
int like[max_place];
int timetake[max_place];
int maxlike[max_time][max_place];
int p,t,minitime;

int max(int a,int b)
{
if(a>=b) return a;
else return b;
}

int mintime(int time[],int p)
{
int i,min=10000;
for(i=0;i<p;i++)
{
if(time[i]<=min) min=time[i];

}
return min;
}

int GetMaxLike(int time,int placeNum)
{
int retMaxLike;
int minitime=mintime(timetake,p);
if(maxlike[time][placeNum]!=-1)
{
retMaxLike=maxlike[time][placeNum];
}
else if(placeNum==0)
{
if(time>=minitime)
retMaxLike=like[placeNum];
else
retMaxLike=0;
}
else if(time>=timetake[placeNum])
{
retMaxLike=max(GetMaxLike(time-timetake[placeNum],placeNum-1)+like[placeNum],GetMaxLike(time,placeNum-1));
}
else
{
retMaxLike=GetMaxLike(time,placeNum-1);
}
maxlike[time][placeNum] =retMaxLike ;
return retMaxLike;

}
int main()
{
for(int i=0; i<max_time; i++)
for(int j=0; j<max_place; j++)
maxlike[i][j] = -1;

cin>>p>>t;
for(int i=0;i<p;i++)
{
cin>>like[i];
cin>>timetake[i];
}
cout<<GetMaxLike(t,p-1)<<endl;

}
不知道哪儿错了，求指教~~

约会王 @ 9 年前

就过了俩

0

张珮华 LV 5 @ 9 年前

麻烦大神给指导！！！竟然拼写错误！我用pascal代入测试数据是过了的！

uses math;
var n,m w,v,i,j:longint;
dp:array[0..1000,0..1000] of longint;
begin
readln(n);
readln(m);
for i:= 1 to n do
begin
readln(v,w);
for j:= w to m do
dp[i,j]:=max(dp[i-1,j],dp[i-1,j-w]+v);
for j:= 0 to w-1 do
dp[i,j]:=dp[i-1,j];
end;
writeln(dp[n,m]);
end.

正在加载...99% @ 9 年前

不能用Math库，自己写个Max函数试试

0

FreeVector LV 6 @ 9 年前

#include <cstdio>

using namespace std;

inline int max(int a,int b) {
return a>b?a:b;
}

int main(void) {
int n=0,v=0;
scanf("%d %d",&n,&v);
int w[n],c[n];
for (int i=0;i<n;++i)
scanf("%d %d",w+i,c+i);
int f[v+1];
for (int i=0;i<=v;++i)
f[i]=0;
for (int i=0;i<n;++i)
for (int j=v;j>=0;--j)
if (j>=c[i])
f[j]=max(f[j],f[j-c[i]]+w[i]);
int ans=0;
for (int i=0;i<v+1;++i)
if (f[i]>ans)
ans=f[i];
printf("%d\n",ans);
return 0;
}

QwQ我好菜

题解

260 条题解

小飞侠的游园方案

信息

状态

开发

支持

题解

260 条题解

小飞侠的游园方案

信息

状态

开发

支持

还没有账户？

登录