题解 - Vijos

2

猫粮寸断 LV 10 @ 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

heyifan LV 10 @ 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

Fop_zz LV 10 @ 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

zhurui LV 8 @ 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

Sky1231 (sky1231) LV 10 @ 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

多啦A梦007 LV 8 @ 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

多啦A梦007 LV 8 @ 2016-07-12 08:21:29

0

1624917200 LV 9 @ 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

神犇 LV 10 @ 2012-09-11 22:48:44

好剪枝无调试一次AC

0

zouxiang LV 8 @ 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

sliverzero LV 8 @ 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

huyou0616 LV 8 @ 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

guori12321 LV 8 @ 2009-10-29 21:40:19

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

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

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

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

0

步惊云 LV 8 @ 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

chengrui LV 10 @ 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

lemon_TsyD LV 9 @ 2009-10-22 23:37:52

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

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

此题方程

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

优化：

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

0

Devil【Law】 LV 8 @ 2009-10-22 21:22:51

比较水的题

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

0

xusc_2009 LV 9 @ 2009-10-22 20:45:02

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

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

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

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

ps：最近做了不少优化题，颇有感触

0

Program饭 LV 8 @ 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

dfx3393521 LV 10 @ 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

题解

92 条题解

更换轮胎

信息

状态

开发

支持

题解

92 条题解

更换轮胎

信息

状态

开发

支持

还没有账户？

登录