题解 - Vijos

2

Sky1231 (sky1231) LV 10 @ 2017-01-21 21:42:04

#include <cstdio>
#include <limits>
#include <algorithm>
using namespace std;

struct node1
{
    int s,b,c;
}a[1001];

int main()
{
    int n,s,b;
    double f[51][51];
    scanf("%d%d%d",&n,&s,&b);
    for (int i=1;i<=n;i++)
        scanf("%d%d%d",&a[i].s,&a[i].b,&a[i].c);
    for (int i=0;i<=s;i++)
        for (int j=0;j<=b;j++)
            f[i][j]=(numeric_limits<double>::max)();
    f[0][0]=0;
    for (int i=1;i<=n;i++)
        for (int j=s;j>=0;j--)
            for (int k=b;k>=0;k--)
                f[j][k]=min(f[j][k],f[max(0,j-a[i].s)][max(0,k-a[i].b)]+a[i].c);
    printf("%.0lf",f[s][b]*2);
}

1

Lifi LV 10 @ 2019-08-02 16:10:47

对S和B做DP，就是不重复背包，不过要注意如果某个坐标小于0，那就直接取0，这样可以允许某一边富余。

#include <iostream>
#include <cstring>
#define ULL unsigned long long

using namespace std;

int s,b;
ULL dp[55][55]={0};

int main()
{
    int n,i,j;
    ULL si,bi,ci;
    cin>>n>>s>>b;
    memset(dp,62,sizeof(dp));
    dp[0][0]=0;
    while(n>0)
    {
        n--;
        cin>>si>>bi>>ci;
        for(i=s;i>=0;i--)
        {
            for(j=b;j>=0;j--)
            {
                if(i<si&&j<bi)
                {
                    dp[i][j]=min(dp[i][j],dp[0][0]+ci);
                }
                else if(i<si)
                {
                    dp[i][j]=min(dp[i][j],dp[0][j-bi]+ci);
                }
                else if(j<bi)
                {
                    dp[i][j]=min(dp[i][j],dp[i-si][0]+ci);
                }
                else
                {
                    dp[i][j]=min(dp[i][j],dp[i-si][j-bi]+ci);
                }
            }
        }
    }
    cout<<dp[s][b]*2<<endl;
    return 0;
}

0

Accepted_upc LV 8 @ 2016-09-12 13:47:31

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define maxn (4000 + 20)
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
using namespace std;
typedef long long int LLI;

LLI sma[maxn],big[maxn],pri[maxn];
LLI dp[maxn][maxn];

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    LLI n,s,b;
    scanf("%lld%lld%lld",&n,&s,&b);
    memset(dp,-1,sizeof(dp));
    for(int i = 1;i <= n;i ++){
        scanf("%lld%lld%lld",&sma[i],&big[i],&pri[i]);
    }
    dp[0][0] = 0;
    for(int i = 1;i <= n;i ++){
        for(int j = s;j >= 0;j --){
            for(int k = b;k >= 0;k --){
                if(dp[j][k] == -1)    continue;
                LLI x = min(j + sma[i],s);
                LLI y = min(k + big[i],b);
                if(dp[x][y] == -1)  dp[x][y] = dp[j][k] + pri[i];
                else                dp[x][y] = min(dp[x][y],dp[j][k] + pri[i]);
            }
        }
    }
    printf("%lld\n",dp[s][b] * 2);
    return 0;
}

0

qig159357 LV 8 @ 2016-06-20 20:23:16

long long 保存答案……
```c++
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long int INF = 9223372036854700000;

int n,S,B;
long long int info[2][100][100],s[1010],b[1010],c[1010];

int main()
{
/*freopen("Girlman","r",stdin);*/
scanf("%d%d%d",&n,&S,&B);
for(int i=1;i<=n;i++)
scanf("%lld%lld%lld",&s[i],&b[i],&c[i]);

info[n%2][0][0]=0;
for(int i=0;i<=S;i++)
for(int j=0;j<=B;j++)
if(i<=s[n]&&j<=b[n]&&(i>0||j>0)) info[n%2][i][j]=c[n];
else if(i>s[n]||j>b[n]) info[n%2][i][j]=INF;
while(--n)
{
int now=n%2;
for(int i=0;i<=S;i++)
for(int j=0;j<=B;j++)
if(i<=s[n]&&j<=b[n]) info[now][i][j]=min(info[now^1][i][j],c[n]);
else info[now][i][j]=min(info[now^1][i][j],info[now^1][i-s[n]<0?0:i-s[n]][j-b[n]<0?0:j-b[n]]==INF ? INF : info[now^1][i-s[n]<0 ? 0 : i-s[n]][j-b[n]<0 ? 0 : j-b[n]]+c[n]);
}
printf("%lld\n",info[1][S][B]*2);
return 0;
}

/* Accepted, time = 169 ms, mem = 684 KiB, score = 100 2016年6月20日星期一 */
```

0

q234rty LV 10 @ 2015-04-17 20:22:14

dp，注意一下边界条件，还有要用int64或Qword,并且最后答案要乘2

Pascal code

function min(a,b:Qword):Qword;
begin
if a<b then exit(a)
else exit(b);
end;
var
n,s,b,i,j,k,j1,k1:longint;
p,t1,t2:array[1..1000] of Qword;
dp:array[0..1000,0..60,0..60] of Qword;
begin
readln(n,s,b);
for i:=1 to n do
readln(t1[i],t2[i],p[i]);
for j:=0 to s do
for k:=0 to b do
if (j<=t1[1]) and (k<=t2[1]) then dp[1,j,k]:=p[1]
else dp[1,j,k]:=1 shl 60;
dp[1,0,0]:=0;
for i:=2 to n do
for j:=s downto 0 do
for k:=b downto 0 do
begin
if j<t1[i] then j1:=0
else j1:=j-t1[i];
if k<t2[i] then k1:=0
else k1:=k-t2[i];
dp[i,j,k]:=min((dp[i-1,j,k]),(dp[i-1,j1,k1]+p[i])); //状态转移
end;
writeln(dp[n,s,b]*2);
end.

0

一方T行 LV 10 @ 2014-08-19 21:44:07

水题水过
program p1428;
var f:array[0..60,0..60] of int64;
a,b,c:array[1..1000] of int64;
n,bb,i,j,cc,k:longint;
//
function min(b,c:int64):int64;
begin
if b>c then exit(c)
else exit(b);
end;
//
function max(b,c:int64):int64;
begin
if b>c then exit(b)
else exit(c);
end;
//
begin
assign(input,'p1428.in');assign(output,'p1428.out');
reset(input);rewrite(output);
read(n,bb,cc);
for i:=1 to n do read(b[i],c[i],a[i]);
for i:=0 to bb do
for j:=0 to cc do f[i,j]:=100000000000;
f[0,0]:=0;
for i:=1 to n do
for j:=bb downto 0 do
for k:=cc downto 0 do
begin
f[j,k]:=min(f[max(0,j-b[i]),max(0,k-c[i])]+a[i],f[j,k]);
end;
write(f[bb,cc]*2);
close(output);
end.

0

renxuandi LV 10 @ 2013-11-03 20:51:23

uses math;
var i,j,k,l,S,B,m,n:Longint;
W1,W2,V:array[1..1000] of Longint;
F:array[0..50,0..50] of Int64;
Begin
Readln(N,S,B);
For i:=1 to N do Readln(W1[i],W2[i],V[i]);
For i:=0 to 50 do
For j:=0 to 50 do F[i,j]:=1 shl 60;
F[0,0]:=0;
For i:=1 to N do
For j:=S downto 0 do
For k:=B downto 0 do
F[j,k]:=Min(F[j,k],F[Max(j-W1[i],0),Max(k-W2[i],0)]+V[i]);
Writeln(F[S,B]*2);
End.

0

鲁大牛 LV 7 @ 2013-03-12 21:45:09

大家别纠结在SI,BI,CI的范围上，可能你们会想F[I][J]来表示小狗和大狗的次数下最优价钱，但发现加上个这么大的si或bi怎么办（也有可能是我低估你们的智商了。。。）。其实只要把多出来的放到F[S,B]中就可以了，因为都是满足情况下的一种状态，可以比较。还有就是数组开INT64！能AC了（01背包）

0

ksj275172111 LV 7 @ 2010-04-16 21:59:39

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：144ms

为什么开到50也能过？？。。。。。

program vijos_1428;

var n,s1,b1:longint;

i,j,k,x,y:longint;

s,b,c:array[1..1000]of int64;

f:array[0..50,0..50]of int64;

begin

readln(n,s1,b1);

for i:=0 to 50 do

for j:=0 to 50 do f:=-1;

for i:=1 to n do

readln(s[i],b[i],c[i]);

f[0,0]:=0;

for k:=1 to n do

for i:=50 downto 0 do

for j:=50 downto 0 do

if f>=0 then

begin

x:=i+s[k];

y:=j+b[k];

if x>s1 then x:=s1;

if y>b1 then y:=b1;

if f[x,y]

0

YY_0227 LV 8 @ 2010-03-27 20:44:03

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

循环搞大点没错！

0

Veili LV 9 @ 2009-11-11 20:17:41

大量级的循环中

加一个max Or min函数，

就会降低3W点的人品——

从不加的0.03s到0.14s的变化。。。

0

Volom@nder LV 8 @ 2009-11-08 15:06:16

这道题没有极限数据，不然类似“3000 3000 1”的数据肯定都wa 到时候这个题的难度就不是1了、、、

0

darin LV 10 @ 2009-10-25 15:56:03

。。。。int64。。。我昏。。

0

474182029 LV 8 @ 2009-09-21 09:50:10

如果需要，你的数组大小要开到更大。因为有可能有种方案大大满足了大小格尔曼的叫声，但是价格却最便宜，交了n次。。。。

0

zgx LV 10 @ 2009-08-19 20:24:47

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

黑牌 LV 10 @ 2009-08-14 22:14:10

实际上本题就是背包...不过有可能单价为0所以初值要全部为maxlongint*maxlongint...而且数组一定要开int64

至于范围问题..数组开0..50,0..50绝对能过,没必要听底下说什么要开到60..当然除非你做法有需要

f表示超过或正好达到要求的最小花费..这样能够有效的节省空间并且保留最优解..如果j>=s那么就只需要存在f里了

0

bi1_1 LV 9 @ 2009-08-14 13:32:13

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：50ms

该个范围，我就没有一次ac了，注意有一点有可能小狗的叫声超过了，但大狗的没过，所以我多开了了一些 f:array[1..51] of array[1..51] of qword;

0

wzc1995 LV 10 @ 2009-08-14 01:04:44

C++猥琐的付初值，

for(i=0;i

0

飘の★ LV 10 @ 2009-08-12 23:11:16

数据范围欺骗了我。。。

看了题解才知道

不是50是60

0

claire_ LV 10 @ 2009-08-11 10:10:36

初值赋的不够大，错了两个点

题解

84 条题解

Pascal code

贪婪格尔曼

信息

状态

开发

支持

题解

84 条题解

Pascal code

贪婪格尔曼

信息

状态

开发

支持

还没有账户？

登录