249 条题解

  • 0
    @ 2006-06-15 09:03:40

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

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

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

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

  • 0
    @ 2006-01-26 10:02:10

    嵌套DP(至少我这么AC的)

    注意转移的表达

  • -1
    @ 2020-05-13 21:35:24
    #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
    @ 2017-09-16 16:00:45
    #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
    @ 2017-01-17 16:42:55

    最短路……

  • -1
    @ 2015-10-28 17:18:41

    最短路+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;
    }

    • @ 2016-03-06 10:32:19

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

  • -1
    @ 2015-10-25 11:01:47

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

  • -1
    @ 2014-08-19 16:15:10

信息

ID
1006
难度
6
分类
动态规划 点击显示
标签
递交数
8986
已通过
2074
通过率
23%
被复制
25
上传者