题解 - Vijos

0

gujoe LV 3 @ 18 年前

又是双重动归吗，为什么小胖办证那么少的人过

0

西门吹牛 LV 3 @ 18 年前

对啊，可以用Floyd算法！

——谁叫我不会DP呢，只好用o(n^3)的算法了。

0

thinxer LV 3 @ 19 年前

郁闷啊，正确率直线下降....除了要注意走的方式以外，还要注意每一层的走法。

最下面一层只能从第一个出发...别的层就不一定了，所以要双重DP，超时了...

精简代码，去掉min函数，虽然写起来麻烦点，不过...过了！

PS:要是pascal有宏定义就好了

0

Coldwings LV 4 @ 19 年前

嵌套DP（至少我这么AC的）

注意转移的表达

-1

hyh5609 LV 10 @ 5 年前

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define INF 0x7ffffabc
#define MAXN 1007
 
void Read(int &p)
{
    p=0;
    int f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
        p=p*10+c-'0',c=getchar();
    p*=f;
}
 
int N,mp[MAXN][MAXN],dp[MAXN][MAXN];
 
void debug()
{
    for(int i=1;i<=N;i++,putchar('\n'))
        for(int j=1;j<=i;j++)
            if(dp[i][j])printf("%d ",dp[i][j]);
}
 
int main()
{
    Read(N);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=i;j++)
            Read(mp[i][j]);
    dp[1][1]=mp[1][1];
    for(int i=2;i<=N;i++)
    {
        for(int j=2;j<i;j++)
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+mp[i][j];
        dp[i][1]=min(dp[i-1][1],dp[i-1][i-1])+mp[i][1];
        dp[i][i]=min(dp[i-1][i-1],dp[i-1][1])+mp[i][i];
        for(int t=1;t<=2;t++)
        {
            for(int j=i-1;j>=1;j--)
                dp[i][j]=min(dp[i][j],dp[i][j+1]+mp[i][j]);
            dp[i][i]=min(dp[i][i],dp[i][1]+mp[i][i]);
 
            for(int j=2;j<=i;j++)
                dp[i][j]=min(dp[i][j],dp[i][j-1]+mp[i][j]);
            dp[i][1]=min(dp[i][1],dp[i][i]+mp[i][1]);
        }
    }
    printf("%d\n",dp[N][1]);
    return 0;
}

-1

pengyou001 LV 8 @ 7 年前

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

const int maxn=1005;
int a[maxn][maxn];
int f[maxn][maxn];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
        cin>>a[i][j];
    f[1][1]=a[1][1];//终点处就直接是该点时间
    for(int i=2;i<=n;i++)//一层一层往上推
    {
        for(int j=2;j<i;j++)//先求出从上一层推出来的最小值
            f[i][j]=min(f[i-1][j],f[i-1][j-1])+a[i][j];
        f[i][1]=min(f[i-1][1],f[i-1][i-1])+a[i][1];//特殊边界点处理
        f[i][i]=min(f[i-1][i-1],f[i-1][1])+a[i][i];//特殊边界点处理
        //同一层更新最优解
        for(int k=i-1;k>0;k--)//从右往左推 从右往左走的情况更新
            f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
        f[i][i]=min(f[i][i],f[i][1]+a[i][i]);

        for(int l=2;l<=i;l++)//从左往右推 从左往右走的情况更新
            f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
            f[i][1]=min(f[i][1],f[i][i]+a[i][1]);

        for(int k=i-1;k>0;k--)//再推一遍从右往左推 从右往左走的情况更新
            f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
            f[i][i]=min(f[i][i],f[i][1]+a[i][i]);

        for(int l=2;l<=i;l++)//再推一遍从左往右推 从左往右走的情况更新
            f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
                f[i][1]=min(f[i][1],f[i][i]+a[i][1]);
    }
    cout<<f[n][1]<<endl;
}

-1

程思元1 LV 8 @ 8 年前

最短路……

-1

wang_yanheng LV 10 @ 9 年前

最短路+1
难点是构图，需要进行一些坑爹的代数运算，还要把点权移到边权上去。由于没有负权回路，故最短路总能输出答案。

#include <stdio.h>
#include <limits.h>

struct edge{
int to, value;
} E[600000][4];
int numEdge[600000];
int queue[1000000];
int dist[600000];
short using[600000];

void addEdge(int from, int to, int value){
E[from][numEdge[from]].to = to;
E[from][numEdge[from]].value = value;
numEdge[from]++;
}
int minPath(int source, int sink, int numV){
int head = 0, tail = 1, i, u;
for(i=0; i<=numV; i++){
dist[i] = LONG_MAX;
using[i] = 0;
}
queue[0] = source;
dist[source] = 0;
using[source] = 1;
while(head < tail){
u = queue[head];
using[u] = 0;
for(i=0; i<numEdge[u]; i++){
if(dist[u] + E[u][i].value < dist[E[u][i].to]){
dist[E[u][i].to] = dist[u] + E[u][i].value;
if(!using[E[u][i].to]){
using[E[u][i].to] = 1;
queue[tail] = E[u][i].to;
tail++;
}
}
}
head++;
}
return dist[sink];
}
int main(){
int height, i, j, value, numV;
scanf("%d", &height);
for(i=0; i<600000; i++)
numEdge[i] = 0;
numV = 0;
for(i=1; i<=height; i++){
for(j=0; j<i; j++){
scanf("%d", &value);
addEdge(numV+j, numV+(j+i-1)%i, value); //left
addEdge(numV+j, numV+(j+i+1)%i, value); //right
if(i > 1){
addEdge(numV+j, numV-i+1+(j+i-2)%(i-1), value); //left-up
addEdge(numV+j, numV-i+1+(j+i-1)%(i-1), value); //right-up
}else{
addEdge(numV+j, height*(height+1)/2, value); //top
}
}
numV += i;
}
printf("%d\n", minPath(numV-height, height*(height+1)/2, numV+1));
return 0;
}

1464942666 @ 9 年前

其实就是搞数学... 我用的是数列求和来搞 点的编号... 然后*Dijkstra*要优先队列优化...

-1

浮光过客 LV 10 @ 9 年前

###Block code
最短路秒杀~！~！~！~！~！~！

-1

hjhk LV 6 @ 10 年前

(www.google.com)

-1

SEX丶Elope LV 6 @ 12 年前

点击查看程序源码+详细题解

题解

251 条题解

晴天小猪历险记之Hill

信息

状态

开发

支持

题解

251 条题解

晴天小猪历险记之Hill

信息

状态

开发

支持

还没有账户？

登录