题解 - Vijos

5

PowderHan LV 10 @ 2017-05-08 09:05:20

/*
哈~一个挺简单的dp的直接就A了
状态应该很好想到
f[i][j]表示当前签证到第i层的第j个房间需要的最小费用
那么一个f[i][j]有三个决策
f[i-1][j],f[i][j-1],f[i][j+1]三个状态转移而来
注意因为同时存在f[i][j-1]和f[i][j+1]
所以在第二维的方向上注定不能一次推出来
应该是先从左往右推一次再从右往左推一次~
这样才能具有无后效性和最优子结构性质了~
那么我们递推出f[][]之后
就找到f[m][]中的最小值
即最后所在的位置(m,p)
那么开始递归打印路线
我们可以很容易通过f[][]来判断当前状态是由哪个状态转移而来
那么我们先递归打印下去
递归边界就是f[1][]的时候直接输出当前坐标就可以return了
在递归结束后才输出自己的坐标
就可以轻松AC~！
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=505;
const int MAXM=105;
const int INF=(1<<30)-1;
int f[MAXM][MAXN];
int w[MAXM][MAXN];
int n,m;
int ans=INF,p;

void init()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&w[i][j]);
    memset(f,0x3f,sizeof(f));
}

void DP()
{
    for(int i=1;i<=n;i++)
        f[1][i]=w[1][i];
    for(int i=2;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
            f[i][j]=f[i-1][j]+w[i][j];
        for(int j=2;j<=n;j++)
            f[i][j]=min(f[i][j],f[i][j-1]+w[i][j]);
        for(int j=n-1;j>=1;j--)
            f[i][j]=min(f[i][j],f[i][j+1]+w[i][j]);
    }
    for(int i=1;i<=n;i++)
    {
        if(f[m][i]<ans)
        {
            ans=f[m][i];
            p=i;
        }
    }
}

void print(int x,int y)
{
    if(x==1)
    {
        cout<<y<<endl;
        return;
    }
    if(f[x-1][y]+w[x][y]==f[x][y])
        print(x-1,y);
    else    if(f[x][y-1]+w[x][y]==f[x][y])
        print(x,y-1);
    else
        print(x,y+1);
    cout<<y<<endl;
}

int main()
{
    init();
    DP();
    print(m,p);
}

2

nicksj LV 8 @ 2017-10-07 22:44:52

最短路写的吐血。。。。没spj

#include<bits/stdc++.h>
#define N 1e9+7
using namespace std;
typedef struct node
{
    int x,y;
    int id;
    int cost;
    int len;
    bool operator<(const node &cx)const
    {   if(cx.cost == cost)
        return cx.len < len;
        return cx.cost < cost;
    }
} point;
priority_queue<node>que;
vector<node>vec[60000];
int d[105][505];
int dlen[105][505];
point ip[105][505];
class memo
{
private:
    int n,m,ma[105][505];
public:
    void in();
    void build();
    void short_path();
};
void memo::in()
{
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d",&ma[i][j]);
        }
    }
}
void memo::build()
{
    for(int i = 1; i <= m; i++)
    {
        vec[0].push_back(node{1,i,i,ma[1][i]});

    }
    if(n >= 2)
    {
        for(int i = 2; i <= n; i++)
        {

            for(int j = 1; j <= m; j++)
            {
                int id = (i-1)*m + j;
                if(j == 1)
                {
                    if(m > 1)
                        vec[id].push_back(node{i,j+1,id + 1,ma[i][j+1]});
                    int ic = (i-2)*m+j;
                    vec[ic].push_back(node{i,j,id,ma[i][j]});
                }
                else if(j == m)
                {
                    if(m > 1)
                        vec[id].push_back(node{i,j-1,id-1,ma[i][j-1]});
                    int ic = (i-2)*m+j;
                    vec[ic].push_back(node{i,j,id,ma[i][j]});
                }
                else
                {
                    vec[id].push_back(node{i,j-1,id-1,ma[i][j-1]});
                    vec[id].push_back(node{i,j+1,id+1,ma[i][j+1]});
                    int ic = (i-2)*m+j;
                    vec[ic].push_back(node{i,j,id,ma[i][j]});
                }
            }

        }
    }
}
void memo::short_path()
{
    while(!que.empty())
        que.pop();
    que.push(node{0,0,0,0,0});
    memset(dlen,0x3f,sizeof(dlen));
    for(int i = 0; i < 105; i++)
        for(int j = 0; j < 505; j++)
            d[i][j] = N;
    node head,tp;
    while(!que.empty())
    {
        head = que.top();
        //printf("%d\n",vec[]);
        que.pop();
        for(int i = 0; i < vec[head.id].size(); i++)
        {
            tp = vec[head.id][i];
            if(head.cost + tp.cost < d[tp.x][tp.y])
            {
                d[tp.x][tp.y] = head.cost  + tp.cost;
                ip[tp.x][tp.y] = node{head.x,head.y,head.id,0,0};
                dlen[tp.x][tp.y] = head.len+1;
                que.push(node{tp.x,tp.y,tp.id,d[tp.x][tp.y],head.len+1});
            }
            else if(head.cost + tp.cost == d[tp.x][tp.y])
            {
                if(head.len + 1 < dlen[tp.x][tp.y])
                {
                     dlen[tp.x][tp.y] = head.len+1;
                     ip[tp.x][tp.y] = node{head.x,head.y,head.id,0,0};
                     que.push(node{tp.x,tp.y,tp.id,d[tp.x][tp.y],head.len+1});
                }
            }
        }
    }
    int maxx = N,ix,iy;
    for(int i = 1;i <= m;i++)
    {
        if(d[n][i] < maxx)
            maxx = d[n][i],ix = n,iy = i;
    }
    for(int i = 2;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            if(j == 1)
            {
                if(dlen[i][j] == dlen[i-1][j]+1&&d[i-1][j] + ma[i][j] == d[i][j])
                {
                   ip[i][j] = node{i-1,j,0,0,0};
                }
                else if(m > 1)
                {
                    ip[i][j] = node{i,j+1,0,0,0};
                }
            }
            else if(j == m)
            {
                 if(dlen[i][j] == dlen[i-1][j]+1&&d[i-1][j] + ma[i][j] == d[i][j])
                {
                   ip[i][j] = node{i-1,j,0,0,0};
                }
                else if(m > 1)
                {
                    ip[i][j] = node{i,j-1,0,0,0};
                }
            }
            else
            {
                if(dlen[i][j] == dlen[i-1][j]+1&&d[i-1][j] + ma[i][j] == d[i][j])
                {
                   ip[i][j] = node{i-1,j,0,0,0};
                }
                else if(dlen[i][j] == dlen[i][j-1]+1&&d[i][j-1] + ma[i][j] == d[i][j])
                {
                    ip[i][j] = node{i,j-1,0,0,0};
                }
                else
                {
                    ip[i][j] = node{i,j+1,0,0,0};
                }
            }
        }
    }
    int path[600];
    int cnt = 0;
    path[cnt++] = iy;
    while(ix!=0)
    {   int ixx,iyy;
        ixx = ip[ix][iy].x;
        iyy = ip[ix][iy].y;
        ix = ixx;
        iy = iyy;
        path[cnt++] = iyy;
    }
    for(int i = cnt-2;i >= 0;i--)
        printf("%d\n",path[i]);
}
int main(void)
{
    memo T;
    T.in();
    T.build();
    T.short_path();
    return 0;
}

1

李明嘉 LV 7 @ 2017-07-22 22:57:31

#1 Accepted 3ms 256.0KiB
#2 Accepted 5ms 896.0KiB
#3 Accepted 10ms 896.0KiB
#4 Accepted 14ms 988.0KiB
#5 Accepted 14ms 896.0KiB
#6 Accepted 1ms 344.0KiB
#7 Accepted 3ms 724.0KiB
#8 Accepted 3ms 384.0KiB
#9 Accepted 7ms 716.0KiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 0x7fffffff;
int m, n;
int a[100 + 5][500 + 5];
int dp[100 + 5][500 + 5];
int pre[100 + 5][500 + 5]; //0表示向下（第一行除外），1表示向右，-1表示向左；
int ans = INF;

void print(int m, int x) {
if(pre[m][x] == 0) {
if(m == 1) {
printf("%d\n", x); return;
}
print(m-1, x);
}
else print(m, x+pre[m][x]);
printf("%d\n", x);
}

int main() {
scanf("%d%d", &m, &n);
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
dp[i][j] = INF;
}
}

for(int j = 1; j <= n; j++)
dp[1][j] = a[1][j];

for(int i = 1; i <= m; i++) {
for(int j = n-1; j >= 1; j--)
if(dp[i][j+1]+a[i][j] < dp[i][j]) {
dp[i][j] = dp[i][j+1] + a[i][j];
pre[i][j] = 1;
}

for(int j = 2; j <= n; j++)
if(dp[i][j-1]+a[i][j] < dp[i][j]) {
dp[i][j] = dp[i][j-1] + a[i][j];
pre[i][j] = -1;
}
for(int j = 1; j <= n; j++)
dp[i+1][j] = dp[i][j]+a[i+1][j];

}

int x, ans = INF;
for(int j = 1; j <= n; j++)
if(dp[m][j] < ans) ans = dp[m][x = j];

print(m, x);
return 0;
}

1

skyhacker LV 7 @ 2009-06-28 12:23:20

#include

int f[101][501]={0},a[101][501],M,N;

int fun(int i,int j)//递归输出路径

{

int n,m;

if(i==1) printf("%d\n",j);

else

{

if(f[j]>f[i][j-1])

{

if(f[i][j-1]>f[i][j+1])

{n=i; m=j+1;}

else{n=i; m=j-1;}

}

else

{

if(f[j]>f[i][j+1])

{n=i; m=j+1;}

else{n=i-1; m=j;}

}

fun(n,m);

printf("%d\n",j);

}

}

int main()

{

int i,j,k,min=0;

scanf("%d %d",&M,&N);

for(i=1;i

0

bjlfzs LV 5 @ 2017-09-29 11:55:58

bfs

0

bjlfzs LV 5 @ 2017-09-29 11:20:13

b.....bfs??

0

feng_lingsong LV 9 @ 2016-09-15 23:54:18

简单dp，条件不说清太流氓了，把注释那几行的顺序改了几遍才AC
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define inf (1 << 30)
#define rep(i, x, y) for (int i = x; i <= y; ++i)

using namespace std;

int m, n, w[128][512], f[128][512], g[128][512];

void print(int fl, int num) {
if (fl == 1) {
printf("%d\n", num);
return;
}
if (g[fl][num] == 1) print(fl - 1, num);
if (g[fl][num] == 2) print(fl, num - 1);
if (g[fl][num] == 3) print(fl, num + 1);
printf("%d\n", num);
}
int main(int argc, const char *argv[]) {
scanf("%d %d", &m, &n);
rep(i, 1, m) rep(j, 1, n) {
scanf("%d", &w[i][j]);
}
rep(i, 1, m) rep(j, 0, n + 1)f[i][j] = inf;
rep(i, 1, n) f[1][i] = w[1][i];
rep(i, 2, m) {

rep(k, 1, n) rep(j, 1, n) {
f[i][j] = min(f[i][j], min(min(f[i - 1][j], f[i][j - 1]), f[i][j + 1]) + w[i][j]);
if (f[i][j] == f[i][j - 1] + w[i][j]) g[i][j] = 2; //这里
if (f[i][j] == f[i][j + 1] + w[i][j]) g[i][j] = 3; //这里
if (f[i][j] == f[i - 1][j] + w[i][j]) g[i][j] = 1; //这里
}
}
/*
rep(i, 1, m) {
rep(j, 1, n) {
printf("%d ", g[i][j]);
}
printf("\n");
}*/
int ans = inf, x;
rep(i, 1, n) {
if (f[m][i] < ans) {
ans = f[m][i]; //这里
x = i;
}
}
print(m, x);
return 0;
}

0

liuyiah LV 10 @ 2016-08-06 21:30:26

最短路写得想撞墙。。好吧还是DP王道
dp[i,j]:=min(dp[i-1,j],dp[i,j-1],dp[i,j+1])+dis[i,j]
程序不发了。。太丑

0

林铮翔 LV 6 @ 2016-08-04 20:49:35

刚刚没打好，再打一次
c++ #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<queue> using namespace std; int m,n; int a[101][501],f[101][501]; void print(int,int); int main() { cin>>m>>n; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) f[1][i]=a[1][i]; for(int i=2;i<=m;i++) { for(int j=1;j<=n;j++) f[i][j]=f[i-1][j]+a[i][j]; for(int j=2;j<=n;j++) f[i][j]=min(f[i][j],f[i][j-1]+a[i][j]); for(int j=n-1;j>=1;j--) f[i][j]=min(f[i][j],f[i][j+1]+a[i][j]); } int ans=0x7fffffff,b; for(int i=1;i<=n;i++) if(f[m][i]<ans) { ans=f[m][i]; b=i; } print(m,b); return 0; } void print(int i,int j) { if(i==1) { cout<<j<<endl; return ; } if(f[i-1][j]+a[i][j]==f[i][j]) { print(i-1,j); cout<<j<<endl; return ; } if(j!=n&&f[i][j+1]+a[i][j]==f[i][j]) { print(i,j+1); cout<<j<<endl; return ; } if(j!=1&&f[i][j-1]+a[i][j]==f[i][j]) { print(i,j-1); cout<<j<<endl; return ; } } /* 3 4 10 10 1 10 2 2 2 10 1 10 10 10 */

0

林铮翔 LV 6 @ 2016-08-04 20:48:27

我想知道你们为什么要写的这么复杂
直接搜嘛

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int m,n;
int a[101][501],f[101][501];
void print(int,int);
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
f[1][i]=a[1][i];
for(int i=2;i<=m;i++)
{
for(int j=1;j<=n;j++)
f[i][j]=f[i-1][j]+a[i][j];
for(int j=2;j<=n;j++)
f[i][j]=min(f[i][j],f[i][j-1]+a[i][j]);
for(int j=n-1;j>=1;j--)
f[i][j]=min(f[i][j],f[i][j+1]+a[i][j]);
}
int ans=0x7fffffff,b;
for(int i=1;i<=n;i++)
if(f[m][i]<ans)
{
ans=f[m][i];
b=i;
}
print(m,b);
return 0;
}
void print(int i,int j)
{
if(i==1)
{
cout<<j<<endl;
return ;
}
if(f[i-1][j]+a[i][j]==f[i][j])
{
print(i-1,j);
cout<<j<<endl;
return ;
}
if(j!=n&&f[i][j+1]+a[i][j]==f[i][j])
{
print(i,j+1);
cout<<j<<endl;
return ;
}
if(j!=1&&f[i][j-1]+a[i][j]==f[i][j])
{
print(i,j-1);
cout<<j<<endl;
return ;
}
}
/*
3 4
10 10 1 10
2 2 2 10
1 10 10 10
*/

0

Kenny10001 LV 7 @ 2016-05-19 16:59:54

我的题解
 我的题解2

0

wang_yanheng LV 10 @ 2016-04-03 22:37:30

原来大家都用的动规，就我一个写最短路...不过思想都一样啦。
不必连边，因为每个点只能访问其左边、右边和上面的节点。根据题意，求的是长度最短的最小花费路径，所以需要开两个数组，一个记录费用，一个记录长度。优先选择费用低的；若费用相同则优先选择长度短的（要是费用长度都相同怎么办？放心没有这么坑爹的点）。还要开多一个数组记录前驱以便输出。SPFA可以做到基本秒杀。

0

yuxiao LV 8 @ 2015-10-12 19:31:08

program xam1;
var n,m,i,j,t:longint;
tot:int64;
a,c,d:array[0..200,0..600]of longint;
g,f:array[0..200,0..600]of int64;

function min(a,b:int64):int64;
begin
if a<b then exit(a) else exit(b);
end;

procedure dfs(x,y:longint);
var xx,yy:longint;
begin
if (x=0)and(y=0) then exit;
xx:=c[x,y];
yy:=d[x,y];
dfs(xx,yy);
writeln(y);
end;
begin
readln(n,m);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
for i:=0 to n+1 do
for j:=0 to m+1 do
begin
g[i,j]:=1000000000000;
f[i,j]:=1000000000000;
end;
//fillchar(g,sizeof(g),\(7f);
//fillchar(f,sizeof(f),\)7f);
for i:=1 to m do
begin
g[1,i]:=a[1,i];
c[1,i]:=0;
d[1,i]:=0;
end;

for i:=2 to n do
begin
for j:=1 to m do
begin
f[i,j]:=min(g[i-1,j],f[i,j-1])+a[i,j];
//if f[i,j]>g[i-1,j]+a[i,j] then begin f[i,j]:=g[i-1,j]+a[i,j]; d[i,j]:=j; c[i,j]:=i-1; end;
//if f[i,j]>f[i,j-1]+a[i,j] then begin f[i,j]:=f[i,j-1]+a[i,j]; c[i,j]:=i; d[i,j]:=j-1; end;
end;
for j:=m downto 1 do
begin
if g[i,j]>g[i-1,j]+a[i,j] then begin g[i,j]:=g[i-1,j]+a[i,j]; c[i,j]:=i-1; d[i,j]:=j; end;
if g[i,j]>g[i,j+1]+a[i,j] then begin g[i,j]:=g[i,j+1]+a[i,j]; c[i,j]:=i; d[i,j]:=j+1; end;
if g[i,j]>f[i,j-1]+a[i,j] then begin g[i,j]:=f[i,j-1]+a[i,j]; c[i,j]:=i; d[i,j]:=j-1; end;
end;
end;
tot:=1000000000000;
for i:=1 to m do
if g[n,i]<tot then begin tot:=g[n,i]; t:=i; end;
dfs(n,t);
end.

0

913027135 LV 8 @ 2015-10-12 09:35:20

测试数据 #0: Accepted, time = 0 ms, mem = 2036 KiB, score = 11
测试数据 #1: Accepted, time = 15 ms, mem = 2036 KiB, score = 11
测试数据 #2: Accepted, time = 15 ms, mem = 2036 KiB, score = 11
测试数据 #3: Accepted, time = 15 ms, mem = 2036 KiB, score = 11
测试数据 #4: Accepted, time = 15 ms, mem = 2036 KiB, score = 11
测试数据 #5: Accepted, time = 3 ms, mem = 2036 KiB, score = 11
测试数据 #6: Accepted, time = 3 ms, mem = 2036 KiB, score = 11
测试数据 #7: Accepted, time = 0 ms, mem = 2036 KiB, score = 11
测试数据 #8: Accepted, time = 15 ms, mem = 2036 KiB, score = 11
Accepted, time = 81 ms, mem = 2036 KiB, score = 99
代码
program a02;
var
i,j,k,l,n,m,g,h,ii,jj,kk,ll:longint;
ans,tot:int64;
f,p:array[0..110,0..510]of longint;
a,aa:array[0..110,0..500]of longint;
d:array[0..100000]of longint;

begin
readln(n,m);
fillchar(f,sizeof(f),\(7f );
fillchar(p,sizeof(p),\)7f);
for i:=1 to n do
for j:=1 to m do
read(f[i,j]);
for i:=1 to m do
begin
p[1,i]:=f[1,i];
a[1,i]:=0;
aa[1,i]:=i;
end;
for i:=1 to n-1 do
begin
for j:=1 to m do
begin
if p[i+1,j]>p[i,j]+f[i+1,j] then
begin
p[i+1,j]:=p[i,j]+f[i+1,j];
a[i+1,j]:=i;
aa[i+1,j]:=j;
end;
if p[i,j+1]>p[i,j]+f[i,j+1] then
begin
p[i,j+1]:=p[i,j]+f[i,j+1];
a[i,j+1]:=i;
aa[i,j+1]:=j;
end;
if p[i,j-1]>p[i,j]+f[i,j-1] then
begin
p[i,j-1]:=p[i,j]+f[i,j-1];
a[i,j-1]:=i;
aa[i,j-1]:=j;
end;
end;
for j:=m downto 1 do
begin
if p[i+1,j]>p[i,j]+f[i+1,j] then
begin
p[i+1,j]:=p[i,j]+f[i+1,j];
a[i+1,j]:=i;
aa[i+1,j]:=j;
end;
if p[i,j+1]>p[i,j]+f[i,j+1] then
begin
p[i,j+1]:=p[i,j]+f[i,j+1];
a[i,j+1]:=i;
aa[i,j+1]:=j;
end;
if p[i,j-1]>p[i,j]+f[i,j-1] then
begin
p[i,j-1]:=p[i,j]+f[i,j-1];
a[i,j-1]:=i;
aa[i,j-1]:=j;
end;
end;
end;

kk:=0;
ans:=maxlongint*100;

for i:=1 to m do
if ans>p[n,i] then
begin
ans:=p[n,i];
kk:=i;
end;
ll:=n;

tot:=1;
d[tot]:=kk;
while a[ll,kk]<>0 do
begin
inc(tot);
d[tot]:=aa[ll,kk];
k:=kk; l:=ll;
ll:=a[l,k];
kk:=aa[l,k];
end;
for i:=tot downto 1 do
writeln(d[i]);
end.

0

zeyong14 LV 8 @ 2015-08-26 18:02:50

真是一道够坑的题，正推，反推，加等号，不加等号，各种尝试.... WA无数遍够的感慨
一定要正推，先左后右，不加等号，如果最终最少费用相同，输出签证少的路。如果签证数也相同，输出较前的。
这里是c++ AC代码，望后来者，且行且珍惜。
都是泪。

测试数据 #0: Accepted, time = 17 ms, mem = 8972 KiB, score = 11

测试数据 #1: Accepted, time = 19 ms, mem = 8984 KiB, score = 11

测试数据 #2: Accepted, time = 15 ms, mem = 8984 KiB, score = 11

测试数据 #3: Accepted, time = 19 ms, mem = 8968 KiB, score = 11

测试数据 #4: Accepted, time = 15 ms, mem = 8972 KiB, score = 11

测试数据 #5: Accepted, time = 1 ms, mem = 8972 KiB, score = 11

测试数据 #6: Accepted, time = 15 ms, mem = 8972 KiB, score = 11

测试数据 #7: Accepted, time = 15 ms, mem = 8972 KiB, score = 11

测试数据 #8: Accepted, time = 31 ms, mem = 8972 KiB, score = 11

Accepted, time = 147 ms, mem = 8984 KiB, score = 99

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 600;
const int M = 600;
LL dp[M][N];
LL s[M][N];
struct opint
{
int x,y;
}pa[M][N];
int m,n,t;
void Printf(int x, int y)
{

if(pa[x][y].x != -1)
Printf(pa[x][y].x,pa[x][y].y);
printf("%d\n",y + 1);
}
int reach(int x, int y)
{

if(pa[x][y].x != -1)
return 1 + reach(pa[x][y].x,pa[x][y].y);
else
return 1;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(dp,0,sizeof(dp));
memset(pa,-1,sizeof(pa));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
scanf("%I64d",&s[i][j]);
for(int i = 0; i < n; i++)
{
if(i == 0)
{
for(int j = 0;j < m; j++)
dp[i][j] = s[i][j];
continue;
}
for(int j = 0;j < m; j++)
{
dp[i][j] = dp[i-1][j] + s[i][j];
pa[i][j].x = i-1;
pa[i][j].y = j;
}
for(int j = 1; j < m; j++)
{
if(dp[i][j-1] + s[i][j] < dp[i][j])
{
dp[i][j] = dp[i][j-1] + s[i][j];
pa[i][j].x = i;
pa[i][j].y = j - 1;
}
}
for(int j = m - 2; j >= 0; j--)
{
if(dp[i][j+1] + s[i][j] < dp[i][j])
{
dp[i][j] = dp[i][j+1] + s[i][j];
pa[i][j].x = i;
pa[i][j].y = j + 1;
}
}
}
LL MIN = dp[n-1][0];
int k = 0;
int num = reach(n-1,k);
for(int i = 1; i < m; i++)
{
if(dp[n-1][i] < MIN)
{
MIN = dp[n-1][i];
k = i;
num = reach(n-1,k);
}
else if(dp[n-1][i] == MIN)
{
if(reach(n-1,i) < num)
{
num = reach(n-1,i);
k = i;
}
}
}
Printf(n-1,k);
}
}

0

hitoby LV 6 @ 2014-10-26 16:30:16

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;

int n,m,a[110][550],ri[110][550],rj[110][550],ans[50010];
int x=m,y=0,k=0,minf=0x7ffffff,p,q;
long long f[110][550];

int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
cin>>m>>n;
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);

for (int i=0;i<=m+1;i++)
for (int j=0;j<=n+1;j++)
{
f[i][j]=0;
ri[i][j]=0;
rj[i][j]=0;
}
for (int i=1;i<=m;i++)
for (int j=0;j<=n;j++)
f[i][j]=0x7ffffff;

for (int i=1;i<=m;i++)
{
for (int j=1;j<=n;j++)
{
if (f[i-1][j]+a[i][j]<f[i][j])
{f[i][j]=f[i-1][j]+a[i][j];ri[i][j]=i-1;rj[i][j]=j;}
if (f[i][j-1]+a[i][j]<f[i][j])
{f[i][j]=f[i][j-1]+a[i][j];ri[i][j]=i;rj[i][j]=j-1;}
}
for (int j=n;j>=1;j--)
{
if (f[i-1][j]+a[i][j]<f[i][j])
{f[i][j]=f[i-1][j]+a[i][j];ri[i][j]=i-1;rj[i][j]=j;}
if (f[i][j+1]+a[i][j]<f[i][j])
{f[i][j]=f[i][j+1]+a[i][j];ri[i][j]=i;rj[i][j]=j+1;}
}
}

/*for (int i=1;i<=m;i++)
{
for (int j=1;j<=n;j++)
printf("%d ",f[i][j]);
cout<<endl;
}

for (int i=1;i<=m;i++)
{
for (int j=1;j<=n;j++)
printf("(%d %d)",ri[i][j],rj[i][j]);
cout<<endl;
} */

int x=m,y=0,k=0,minf=0x7ffffff;
for (k=1;k<=n;k++) if (f[x][k]<minf) {minf=f[x][k];y=k;};

k=1;ans[k]=y;
while (x!=1)
{
k++;ans[k]=rj[x][y];
int p=x,q=y;
x=ri[p][q];
y=rj[p][q];

}
for (;k>0;k--) cout<<ans[k]<<endl;

fclose(stdin);
fclose(stdout);
}

求大神解释为什么老是ER

0

赵鋆峰 LV 10 @ 2014-03-29 19:36:37

测试数据 #0: Accepted, time = 0 ms, mem = 1536 KiB, score = 11
测试数据 #1: Accepted, time = 15 ms, mem = 1532 KiB, score = 11
测试数据 #2: Accepted, time = 15 ms, mem = 1536 KiB, score = 11
测试数据 #3: Accepted, time = 31 ms, mem = 1536 KiB, score = 11
测试数据 #4: Accepted, time = 31 ms, mem = 1532 KiB, score = 11
测试数据 #5: Accepted, time = 0 ms, mem = 1532 KiB, score = 11
测试数据 #6: Accepted, time = 0 ms, mem = 1532 KiB, score = 11
测试数据 #7: Accepted, time = 0 ms, mem = 1536 KiB, score = 11
测试数据 #8: Accepted, time = 15 ms, mem = 1540 KiB, score = 11
听了某大牛的正反艘之后时间明显长进！orz

0

赵鋆峰 LV 10 @ 2014-03-29 19:32:29

const max=100000000000000000;
var f:array[0..101,0..501] of int64;
a:array[0..101,0..501] of longint;
pre:array[0..51001] of longint;
i,j,m,n,num:longint;
min:int64;
flag:boolean;
procedure compare(x,y:int64);
begin
if f[x,y]+a[i,j]<f[i,j] then
begin
flag:=false;
f[i,j]:=f[x,y]+a[i,j];
pre[i*m+j]:=x*m+y;
end;
end;
procedure print(x:longint);
begin
if x<=2*m then writeln(x-m)
else
begin
print(pre[x]);
while x>m do x:=x-m;
if m=1 then writeln('1') else writeln(x);
end;
end;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do begin read(a[i,j]);f[i,j]:=max;end;
readln;
end;
for i:=1 to m do begin f[1,i]:=a[1,i];pre[m+i]:=m+i;end;
for i:=1 to n do begin f[i,0]:=max;f[i,m+1]:=max;end;
for i:=2 to n do
begin
repeat
flag:=true;
for j:=1 to m do
begin
compare(i-1,j);
compare(i,j-1);
compare(i,j+1);
end;
until flag;
end;
min:=max;
for i:=1 to m do if f[n,i]<min then begin min:=f[n,i];num:=n*m+i;end;
print(num);
end.
不容易啊！时间有点儿惨不忍睹……
测试数据 #0: Accepted, time = 0 ms, mem = 1536 KiB, score = 11
测试数据 #1: Accepted, time = 218 ms, mem = 1536 KiB, score = 11
测试数据 #2: Accepted, time = 234 ms, mem = 1536 KiB, score = 11
测试数据 #3: Accepted, time = 31 ms, mem = 1536 KiB, score = 11
测试数据 #4: Accepted, time = 31 ms, mem = 1536 KiB, score = 11
测试数据 #5: Accepted, time = 0 ms, mem = 1536 KiB, score = 11
测试数据 #6: Accepted, time = 0 ms, mem = 1540 KiB, score = 11
测试数据 #7: Accepted, time = 0 ms, mem = 1540 KiB, score = 11
测试数据 #8: Accepted, time = 15 ms, mem = 1540 KiB, score = 11

0

csw LV 8 @ 2012-10-14 16:35:04

记忆化搜索秒杀？

├ 测试数据 01：答案正确... (0ms, 1752KB)

├ 测试数据 02：答案正确... (0ms, 1752KB)

├ 测试数据 03：答案正确... (0ms, 1752KB)

├ 测试数据 04：答案正确... (0ms, 1752KB)

├ 测试数据 05：答案正确... (0ms, 1752KB)

├ 测试数据 06：答案正确... (0ms, 1752KB)

├ 测试数据 07：答案正确... (0ms, 1752KB)

├ 测试数据 08：答案正确... (0ms, 1752KB)

├ 测试数据 09：答案正确... (0ms, 1752KB)

0

843279365 LV 8 @ 2012-07-24 14:47:31

编译通过...

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

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

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

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

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

├ 测试数据 08：运行时错误...|错误号: 202

├ 测试数据 09：答案错误...程序输出比正确答案长

彻底悲剧了

题解

174 条题解

小胖办证

信息

状态

开发

支持

题解

174 条题解

小胖办证

信息

状态

开发

支持

还没有账户？

登录