题解

84 条题解

  • 2
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2015-04-17 20:22:14

    dp,注意一下边界条件,还有要用int64Qword,并且最后答案要乘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
    @ 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
    @ 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
    @ 2013-03-12 21:45:09

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

  • 0
    @ 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
    @ 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
    @ 2009-11-11 20:17:41

    大量级的循环中

    加一个max Or min函数,

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

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

  • 0
    @ 2009-11-08 15:06:16

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

  • 0
    @ 2009-10-25 15:56:03

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

  • 0
    @ 2009-09-21 09:50:10

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

  • 0
    @ 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
    @ 2009-08-14 22:14:10

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

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

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

  • 0
    @ 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
    @ 2009-08-14 01:04:44

    C++猥琐的付初值,

    for(i=0;i

  • 0
    @ 2009-08-12 23:11:16

    数据范围欺骗了我。。。

    看了题解才知道

    不是50是60

  • 0
    @ 2009-08-11 10:10:36

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

信息

ID
1428
难度
6
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
1541
已通过
407
通过率
26%
被复制
1
上传者