题解

92 条题解

  • 2
    @ 2019-06-27 21:59:11
    //很不错的一道DP
    //首先很容易可以想到,用dp[i][j]来表示跑完第i圈时轮胎为j的最优解
    //关键在于更新,假如我们暴力更新的话是n^3的复杂度,因此需要优化
    //可以发现这样一个性质:如果我们要换轮胎,那么我们一定会用上一圈用时最少的情况去更新它
    //这样就比较简单了,在每一圈,我们找一下上一圈用时最少的情况,用它去更新这一圈
    //同时维护一下不换轮胎的情况
    #include<iostream>
    using namespace std;
    int dp[3010][3010],map[3010][3010];
    int main()
    {
        int n,m,i,j,c,x,ans=0x3f3f3f3f;
        cin>>n>>m>>c;
        for(i=1;i<=n;i++)
         for(j=1;j<=m;j++)
          cin>>map[i][j];
        for(i=1;i<=m;i++)
         dp[1][i]=map[1][i];
        for(i=2;i<=n;i++)
        {
            x=0x3f3f3f3f;
            for(j=1;j<=m;j++)
             if(dp[i-1][j]<x)
              x=dp[i-1][j];
            for(j=1;j<=m;j++)
              dp[i][j]=min(x+c,dp[i-1][j])+map[i][j];
        }
        for(i=1;i<=m;i++)
         ans=min(ans,dp[n][i]);
        cout<<ans;
        return 0;
    }
    
  • 1
    @ 2018-11-21 19:37:42
    #include <stdlib.h>
    #include <assert.h>
    #define INF (1 << 29)
    
    int min(int a, int b) {
        return (a > b ? b : a);
    }
    
    int main() {
        int i, j, n, c, m, ans;
        int **dp;
        int **time;
        int *mini;
        scanf("%d%d%d", &n, &m, &c);
        dp = calloc(n + 2, sizeof(int *));
        mini = calloc(n + 2, sizeof(int));
        time = calloc(n + 2, sizeof(int *));
        for (i = 0 ; i <= n; i++) {
            dp[i] = calloc(m + 2, sizeof(int));
            time[i] = calloc(m + 2, sizeof(int));
        }
        
        for (i = 1; i <= n; i++) {
            mini[i] = INF;
            for (j = 1; j <= m; j++) {
                scanf("%d", &time[i][j]);
            }
        }
        
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= m; j++) {
                dp[i][j] = min(dp[i-1][j] + time[i][j], c + mini[i-1] + time[i][j]);
                mini[i] = min(mini[i], dp[i][j]);
            }
        }
        
        ans = INF;
        for (i = 1; i <= m; i++) {
            ans = min(ans, dp[n][i]);
        }
        printf("%d\n", ans);
        
        for (i = 0 ; i <= n; i++) {
            free(dp[i]);
            free(time[i]);
        }
        free(dp);
        free(time);
        free(mini);
        return 0;
    }
    
    
  • 1
    @ 2017-05-25 15:08:08

    一个显然成立的条件:如果换轮胎的话,前一圈是什么轮胎,与当前解无关,只要一个最小值就可以了
    接下来就可以把很显然的n^3dp优化到n^2dp,然后就ac了

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <queue>
    #include <string>
    #include <map>
    #include <cstring>
    #include <ctime>
    #include <vector>
    #define inf 1e9
    #define ll long long
    #define For(i,j,k) for(int i=j;i<=k;i++)
    #define Dow(i,j,k) for(int i=k;i>=j;i--)
    using namespace std;
    int f[1001][1001],Mi[1001],a[1001][1001],n,m,t,ans;
    int main()
    {
        scanf("%d%d%d",&n,&m,&t);
        For(i,1,n)  Mi[i]=1e9;
        ans=1e9;
        For(i,1,n) 
            For(j,1,m)
                scanf("%d",&a[j][i]);
        For(i,1,m)  f[0][i]=0;
        For(i,1,n)
            For(j,1,m)
            {
                f[i][j]=min(f[i-1][j]+a[j][i],Mi[i-1]+t+a[j][i]);
                Mi[i]=min(Mi[i],f[i][j]);
            }
        For(i,1,m)  ans=min(ans,f[n][i]);
        printf("%d",ans);
    }
         
    
  • 1
    @ 2009-11-03 12:36:21

    简单的说这是一道“换与不换”的问题。

    考虑这么一个动态转移方程(i代表圈数,j代表换轮胎j,a第i圈第j个跑的时间)f=min(f+a,min+换轮胎时间+a);

    阶段的划分:第i圈,i阶段=i阶段的最小值+考虑换j个轮胎的本圈最小值。

    Min的两种时间的运算:(1)引进上一圈最小值,由另一个轮胎最小值耗时加上换轮胎时间和轮胎j完成一圈时间min+换轮胎时间+a(2)上一圈用的就是本轮胎,不需加换轮胎时间f+a。

    无后效性:由于加上了换轮胎的时间,所以就存在上一圈用什么轮胎,是否要用时间跟换的问题。有两种解法,第一种是把上一圈最小值用什么轮胎j记录下来,再判断当f=min时不换轮胎。但是,所有的最小是取自f[上一圈,1到M所有轮胎],也就是说最小值在上一圈是有记录的。在f不为上一次最小值时,同样是用轮胎j,就看换轮胎时引进上一圈最小值(min+换轮胎时间+a)和继续使用轮胎j(f+a)哪个大;如果f[j]为上一次的min,仍假定使用轮胎j,只有一种可能,不换轮胎继续跑下去,那么f=min,方程中后面一项加换轮胎时间的值就是多余的了。所以min与f[j]存在无后效性。

    求上一圈min值:既然存在无后效性,那么找计算f用到的上一圈最小值,只需在上一层循环f找出最小值。注意,min的初值是maxlongint,否则不方便比较。提示一下f[最后一圈,换所有的轮胎]的min就是答案,不需要再找一次。

    最后简化:去掉圈数维:f[j]:=min(f[j]+a,上一圈最小时间+a+换轮胎时间);

    Program luntai;

    var

    f:array[1..1001]of longword;

    a:array[1..1000,1..1000]of longword;

    i,j,n,m,c,little,who:longword;

    function min(a,b:longword):longword;

    begin if a>b then min:=b else min:=a; end;

    Begin

    readln(n,m,c);

    for i:=1 to m do f[i]:=0;

    for i:=1 to n do

    begin

    for j:=1 to m-1 do

    read(a);

    readln(a);

    end;

    little:=maxlongint;

    for i:=1 to n do

    begin

    who:=maxlongint;

    for j:=1 to m do

    begin

    f[j]:=min(f[j]+a,little+a+c);

    if f[j]

  • 0
    @ 2017-03-06 17:25:07
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <limits>
    #define rn 1000
    #define rm 1000
    using namespace std;
    
    int n,m,c,t[rn+1][rm+1],f[rn+1][rm+1];
    
    int main()
    {
        scanf("%d%d%d",&n,&m,&c);
        memset(f,0,sizeof(f));
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                scanf("%d",&t[i][j]),f[i][j]=(numeric_limits<int>::max)();
        for (int i=1;i<=n;i++)
        {
            int mint=(numeric_limits<int>::max)();
            for (int j=1;j<=m;j++)
            {
                f[i][j]=min(f[i][j],f[i-1][j]+t[i][j]);
                mint=min(mint,f[i-1][j]);
            }
            for (int j=1;j<=m;j++)
                f[i][j]=min(f[i][j],mint+c+t[i][j]);
        }
        int ans=(numeric_limits<int>::max)();
        for (int i=1;i<=m;i++)
            ans=min(ans,f[n][i]);
        printf("%d\n",ans);
    }
    
  • 0
    @ 2016-07-12 08:23:22

    ![#include<iostream>
    #include<iomanip>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    long long a[1001][1001]={0};
    long long b[1051][1051]={0};
    int i,j,k,m,n,o,p,s,t,js,maxx,c,mi;
    using namespace std;
    int main()
    {
    scanf("%d%d%d",&n,&m,&c);
    for(j=1;j<=m;j++) a[0][j]=0;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {
    scanf("%d",&a[i][j]);
    }
    for(i=1;i<=n;i++)
    {
    mi=b[i-1][1];
    for(j=1;j<=m;j++)
    {
    if(mi>b[i-1][j]) mi=b[i-1][j];
    }
    for(j=1;j<=m;j++)
    {
    b[i][j]=(b[i-1][j]+a[i][j]);
    if(mi+c<b[i-1][j]) b[i][j]=mi+c+a[i][j];
    }
    }
    mi=b[n][1];
    for(j=1;j<=m;j++) if(b[n][j]<mi)mi=b[n][j];
    printf("%d",mi);
    return 0;
    }
    ](#include<iostream>
    #include<iomanip>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    long long a[1001][1001]={0};
    long long b[1051][1051]={0};
    int i,j,k,m,n,o,p,s,t,js,maxx,c,mi;
    using namespace std;
    int main()
    {
    scanf("%d%d%d",&n,&m,&c);
    for(j=1;j<=m;j++) a[0][j]=0;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {
    scanf("%d",&a[i][j]);
    }
    for(i=1;i<=n;i++)
    {
    mi=b[i-1][1];
    for(j=1;j<=m;j++)
    {
    if(mi>b[i-1][j]) mi=b[i-1][j];
    }
    for(j=1;j<=m;j++)
    {
    b[i][j]=(b[i-1][j]+a[i][j]);
    if(mi+c<b[i-1][j]) b[i][j]=mi+c+a[i][j];
    }
    }
    mi=b[n][1];
    for(j=1;j<=m;j++) if(b[n][j]<mi)mi=b[n][j];
    printf("%d",mi);
    return 0;
    }
    ](#include<iostream>
    #include<iomanip>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    long long a[1001][1001]={0};
    long long b[1051][1051]={0};
    int i,j,k,m,n,o,p,s,t,js,maxx,c,mi;
    using namespace std;
    int main()
    {
    scanf("%d%d%d",&n,&m,&c);
    for(j=1;j<=m;j++) a[0][j]=0;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {
    scanf("%d",&a[i][j]);
    }
    for(i=1;i<=n;i++)
    {
    mi=b[i-1][1];
    for(j=1;j<=m;j++)
    {
    if(mi>b[i-1][j]) mi=b[i-1][j];
    }
    for(j=1;j<=m;j++)
    {
    b[i][j]=(b[i-1][j]+a[i][j]);
    if(mi+c<b[i-1][j]) b[i][j]=mi+c+a[i][j];

    }

    }
    mi=b[n][1];
    for(j=1;j<=m;j++) if(b[n][j]<mi)mi=b[n][j];
    printf("%d",mi);
    return 0;
    }
    ](http://www.baidu.com)

  • 0
    @ 2016-07-12 08:21:29

    #include<iostream><br>
#include<iomanip><br>
#include<cstdio><br>
#include<cstdlib><br>
#include<cmath><br>
long long a[1001][1001]={0};<br>
long long b[1051][1051]={0};<br>
int i,j,k,m,n,o,p,s,t,js,maxx,c,mi;<br>
using namespace std;<br>
int main()<br>
{<br>
    scanf("%d%d%d",&n,&m,&c);<br>
    for(j=1;j<=m;j++) a[0][j]=0;<br>
    for(i=1;i<=n;i++)<br>
    for(j=1;j<=m;j++)<br>
    {<br>
        scanf("%d",&a[i][j]);<br>
    }<br>
    for(i=1;i<=n;i++)<br>
    {<br>
         mi=b[i-1][1];<br>
         for(j=1;j<=m;j++)<br>
         {<br>
             if(mi>b[i-1][j]) mi=b[i-1][j];<br>
         }<br>
         for(j=1;j<=m;j++)<br>
         {<br>
         b[i][j]=(b[i-1][j]+a[i][j]);<br>
         if(mi+c<b[i-1][j]) b[i][j]=mi+c+a[i][j];  <br>
         }          <br>
    }<br>
    mi=b[n][1];<br>
    for(j=1;j<=m;j++) if(b[n][j]<mi)mi=b[n][j];<br>
    printf("%d",mi);<br>
    return 0;<br>
}<br>

  • 0
    @ 2016-03-03 20:25:22

    编译成功

    Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
    Copyright (c) 1993-2015 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    foo.pas(31,33) Warning: Variable "least" does not seem to be initialized
    Linking foo.exe
    36 lines compiled, 0.0 sec, 27808 bytes code, 1268 bytes data
    1 warning(s) issued
    测试数据 #0: Accepted, time = 2375 ms, mem = 4724 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 4720 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 4724 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 4724 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 4724 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 4720 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 4720 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 4724 KiB, score = 10
    测试数据 #8: Accepted, time = 312 ms, mem = 4720 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 4720 KiB, score = 10
    Accepted, time = 2717 ms, mem = 4724 KiB, score = 100
    测试数据第一行……
    这也过
    我就笑笑.

  • 0
    @ 2012-09-11 22:48:44

    好剪枝 无调试一次AC

  • 0
    @ 2010-04-13 19:07:01

    我也是一次AC 记忆化搜索,33行。不过......

    时间限制 Time Limitation

    各个测试点1s

    编译通过...

    ├ 测试数据 01:答案正确... 2212ms

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

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

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

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

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

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

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

    ├ 测试数据 09:答案正确... 166ms

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

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

    Accepted 有效得分:100 有效耗时:2378ms

    难道这就是传说中的RP???

  • 0
    @ 2010-03-10 19:20:38

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

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

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

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

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

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

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

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

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

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

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

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

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

    for i:=2 to n do

    begin

    for j:=1 to m do

    begin

    read(a);

    if min+c+af then miner:=f;

    end;

    min:=miner;

    miner:=maxlongint*maxlongint;

    end;

    纪念N年难得一次的一次AC

    转移方程为f:=min(f+a,lastmin+c+a)

  • 0
    @ 2009-11-10 00:04:30

    编译通过...

    ├ 测试数据 01:答案正确... 212ms

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

    ├ 测试数据 03:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 04:答案错误... ├ 标准行输出

     ├ 错误行输出

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

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

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

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

    ├ 测试数据 09:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 10:答案错误... ├ 标准行输出

     ├ 错误行输出

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

    Unaccepted 有效得分:60 有效耗时:212ms

    哪里错了啊...各位高手帮忙看看

    program kk;

    var tot,s,c,i,j,k,m,n:longint;

    f:array[0..2001,0..2001] of longint;

    t:array[1..2001,1..2001] of longint;

    min:array[1..2001] of longint;

    begin

    read(n,m,c);

    for i:=1 to n do

    for j:=1 to m do

    read(t);

    for i:=0 to n do

    for j:=0 to m do

    f:=maxlongint;

    for i:=1 to m do f[1,i]:=t[1,i];

    for i:=1 to m do

    min[i]:=maxlongint;

    for i:=1 to m do if min[1]>f[1,i] then min[1]:=f[1,i];

    for i:=2 to n do

    for j:=1 to m do

    begin

    f:=f+t;

    if f>(min+t+c) then

    f:=min+t+c;

    if ff[n,i] then tot:=f[n,i];

    write(tot);

    end.

  • 0
    @ 2009-10-29 21:40:19

    受打击了。这么水的题做了快一个半小时。

    想复杂了。两种决策:换或不换。

    上次最佳的时间加换胎时间 和 不换的时间比较,取min,再加上a就这样。

    一点技巧:for i:=1 to n+1 do 这样最后的min就是ans,不用再找一次。

  • 0
    @ 2009-10-29 17:24:39

    初始化:

    for i:=1 to m do

    f[1,i]:=a[1,i];

    在上一层f中,找出最小值min,对于当前状态f,只需比较min+c和f即可

  • 0
    @ 2009-10-23 19:11:39

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    俄,难道我是秒杀第一人?

    pascal,而且没用滚动数组,空间复杂度N*M

    f表示到第I圈,用第J种轮胎.........

    对于转移,

    1.f->f

    2.f->f

    N*M的时间复杂度,所以秒杀了......

    可能是评测机问题..........

    sunny我也好慢的,用这台新机器(Evolution SmdCn)就秒杀了,囧

  • 0
    @ 2009-10-22 23:37:52

    做得太急了 前面看着的范围 后面就 忘了

    这么水的优化 下次做题一定不要心急!还有提交代码前一定要审核 又导致一次无输出。。。。

    此题方程

    f[i][j] = min(f[j],f[k]+c)+t[i][j];

    优化:

    找最小值的过程 在每一次i 循环中 都算出当前i的f中俄最小值 然后下一个i直接转移

  • 0
    @ 2009-10-22 21:22:51

    比较水的题

    只要有个变量储存上一圈的最小值就行了

  • 0
    @ 2009-10-22 20:45:02

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

    好像挺快的恩,我觉得我的程序还比较简短,完了还用了滚动数组。

    最大的优化就是决策实际上只有两个,上一层的最小值或者是不换轮胎,这样复杂度只有O(n^2),是很快的吧

    ***|\**|\**|\**|\**|\**|\**|\**|\**|\**|\**|\***|*

    ps:最近做了不少优化题,颇有感触

  • 0
    @ 2009-10-05 12:35:43

    今天在四中听老师讲的,实现了一下。

    第一次写滚动数组。

    #include

    #include

    long i,j,k,t[1001][1001],f[2][1001]={0},p,q,min;

    int main()

    {

    long n,m,c;

    scanf("%ld %ld %ld",&n,&m,&c);

    for(i=0;i

  • 0
    @ 2009-09-19 17:56:46

    program dx;

    var

    i,j,n,m,c,min,who,a:longint;

    f:array[0..1001]of longint;

    begin

    read(n,m,c); min:=0;

    for i:=1 to n do begin

    who:=maxlongint;

    for j:=1 to m do begin

    read(a);

    f[j]:=f[j]+a;

    if min+c+a

信息

ID
1421
难度
4
分类
动态规划 点击显示
标签
递交数
1083
已通过
424
通过率
39%
上传者