64 条题解

  • 2
    @ 2016-10-15 20:40:36
    #include<iostream>
    #define INF 1000000
    using namespace std;
    struct tra{
        int s;
        int dist;
    };
    tra car[5];
    int ans=INF;
    int n,dist[101][101];
    void dfs(int s){
        int i; 
        if(s==n){
            ans=min(ans,car[1].dist+car[2].dist+car[3].dist);
            return;
        }
        else{
            for(i=1;i<=3;i++){
                car[i].dist+=dist[car[i].s][s+1];
                int t=car[i].s;
                car[i].s=s+1;
                dfs(s+1);
                car[i].s=t;
                car[i].dist-=dist[car[i].s][s+1];
            }
        }
        
    }
    int main(){
        int i,j;
        cin>>n;
        for(i=1;i<=n-1;i++){
            for(j=i+1;j<=n;j++){
                cin>>dist[i][j];
            }
        }
        for(i=1;i<=3;i++){
            car[i].dist=0;
            car[i].s=1;
        }
        dfs(1);
        cout<<ans;
        return 0;
    }
    
  • 1
    @ 2017-12-06 14:31:42

    dp可过:先跑floyed,求出两点之间的最短距离,然后通过dp[i][j][k]值向后更新(i>j>k),即可。

    #include <iostream>
    #include <cstdio>
    using namespace std;
    const int mod=2333333;
    int head[mod+10],to[mod+10],next[mod+10],tot;
    void add(int a)
    {
        to[++tot]=a;
        next[tot]=head[a%mod];
        head[a%mod]=tot;
    }
    int main()
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int x;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            add(x);
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&x);
            bool flag=false;
            for(int j=head[x%mod];j;j=next[j])
            {
                if(to[j]==x)
                {
                    flag=true;
                    printf("YES\n");
                    break;
                }
            }
            if(flag==false) printf("NO\n");
        }
    }
    
  • 1
    @ 2016-07-17 17:16:16

    /*思路:dp

    dp[i][j][k]表示第一辆车在第i个城市,第二辆车在第j个城市,第三辆车在第k个城市的最小路径;

    初始化:f[1][1][1]=0,其余为Max
    now表示当前到达的最远的城市(即now=max(i,j,k))
    f[now+1][j][k]=min(f[now+1][j][k],f[i][j][k]+a[i][now+1])
    f[i][now+1][k]=min(f[i][now+1][k],f[i][j][k]+a[j][now+1])
    f[i][j][now+1]=min(f[i][j][now+1],f[i][j][k]+a[k][now+1])
    在所有的now=n时,记录最小值。*/

    #include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<stdlib.h>
    5 #include<string.h>
    6 #include<math.h>
    7 #include<queue>
    8 using namespace std;
    9 typedef long long LL;
    10 int dp[105][105][105];
    11 int nn[200][200];
    12 const int N=1e9;
    13 int main(void)
    14 {
    15 int i,j,k;
    16 while(scanf("%d",&k)!=EOF)
    17 {
    18 int x,y;
    19 for(i=1; i<k; i++)
    20 {
    21 for(j=i+1;j<=k;j++)
    22 {
    23 scanf("%d",&nn[i][j]);
    24 }
    25 }
    26 for(i=0; i<105; i++)
    27 {
    28 for(j=0; j<105; j++)
    29 {
    30 for(x=0; x<105; x++)
    31 {
    32 dp[i][j][x]=N;
    33 }
    34 }
    35 }
    36 int ans=1e9;
    37 dp[1][1][1]=0;
    38 for(i=1; i<k; i++)
    39 {
    40 for(j=1; j<k; j++)
    41 {
    42 for(x=1; x<k; x++)
    43 {
    44 int xx=max(i,j);
    45 xx=max(x,xx);
    46 dp[xx+1][j][x]=min(dp[xx+1][j][x],dp[i][j][x]+nn[i][xx+1]);
    47 dp[i][xx+1][x]=min(dp[i][xx+1][x],dp[i][j][x]+nn[j][xx+1]);
    48 dp[i][j][xx+1]=min(dp[i][j][xx+1],dp[i][j][x]+nn[x][xx+1]);
    49 if(xx+1==k)
    50 {ans=min(dp[xx+1][j][x],ans);
    51 ans=min(dp[i][j][xx+1],ans);
    52 ans=min(ans,dp[i][xx+1][x]);
    53 }
    54 }
    55 }
    56 }
    57 printf("%d\n",ans);
    58 }
    59 return 0;
    60 }

  • 1
    @ 2015-04-28 13:17:45

    这题数据太弱,正解应该是三维的记忆搜索。很多人的贪心都是错的
    如:
    input:
    6
    1 2 1 1 10000
    10 10000 10000 10000
    10000 100 10000
    100 10000
    1

    output
    14

    输出105的都是贪心,是错误的。答案应该是14。
    var a:array[0..100,0..100] of longint;
    b:array[1..100,1..100,1..100] of longint;
    n,m,i,j,k,l:longint;

    function minn(x,y:longint):longint;
    begin
    if x=0 then exit(y);
    if y=0 then exit(x);
    if x<y then exit(x)
    else exit(y);
    end;
    function pan(x,y,z:longint):boolean;
    begin
    pan:=false;
    if x>=z-1 then exit(true);
    if y>=z-1 then exit(true);
    end;
    begin
    read(n);
    for i:=1 to n do
    for j:=i+1 to n do
    begin
    read(a[i,j]);
    a[j,i]:=a[i,j];
    end;
    for i:=1 to n do
    for j:=1 to n do
    for k:=1 to n do
    begin
    if k>1 then
    begin
    b[i,j,k]:=minn(b[i,j,k],b[i,j,k-1]+a[k-1,k]);
    if pan(i,j,k) then
    for l:=1 to k-1 do
    b[i,j,k]:=minn(b[i,j,k],b[i,j,l]+a[l,k]);
    end;

    if j>1 then
    begin
    b[i,j,k]:=minn(b[i,j,k],b[i,j-1,k]+a[j-1,j]);
    if pan(i,k,j) then
    for l:=1 to j-1 do
    b[i,j,k]:=minn(b[i,j,k],b[i,l,k]+a[l,j]);
    end;

    if i>1 then
    begin
    b[i,j,k]:=minn(b[i,j,k],b[i-1,j,k]+a[i-1,i]);
    if pan(k,j,i) then
    for l:=1 to i-1 do
    b[i,j,k]:=minn(b[i,j,k],b[l,j,k]+a[l,i]);
    end;
    end;

    for i:=1 to n do
    for j:=1 to n do
    m:=minn(m,b[i,j,n]);
    for i:=1 to n do
    for k:=1 to n do
    m:=minn(m,b[i,n,k]);
    for j:=1 to n do
    for k:=1 to n do
    m:=minn(m,b[n,j,k]);
    writeln(m);
    end.

  • 0
    @ 2019-07-17 20:11:42

    dfs
    cur表示目前到达的最远的城市,car1表示第一辆车到达的城市,car2,car3以此类推,dist为目前的距离

    #include<bits/stdc++.h>
    using namespace std;
    int n,a[110][110],ans=1e9;
    void dfs(int cur,int car1,int car2,int car3,int dist){
        if(cur==n){
            ans=min(ans,dist);
            return;
        }
        dfs(cur+1,cur+1,car2,car3,dist+a[car1][cur+1]);
        dfs(cur+1,car1,cur+1,car3,dist+a[car2][cur+1]);
        dfs(cur+1,car1,car2,cur+1,dist+a[car3][cur+1]);
        return;
    }
    int main(){
        scanf("%d",&n); 
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                scanf("%d",&a[i][j]);   
            }
        }
        dfs(1,1,1,1,0);
        printf("%d\n",ans);
        return 0;
    }
    
  • 0
    @ 2016-09-01 20:32:18

    题意不明,只需要一辆车到终点即可,测试数据都看了半天
    #include <cstdio>
    int max(int a,int b){
    return a>b?a:b;
    }
    int n,map[110][110];
    int ans=99999999;
    void dfs(int dist,int city,int c1,int c2,int c3){
    if(c1==n||c2==n||c3==n){
    ans=ans<dist?ans:dist;
    return;
    }
    for(int i=c1+1;i<=city;i++)
    dfs(dist+map[c1][i],city,i,c2,c3);
    dfs(dist+map[c1][city+1],city+1,city+1,c2,c3);

    for(int i=c2+1;i<=city;i++)
    dfs(dist+map[c2][i],city,c1,i,c3);
    dfs(dist+map[c2][city+1],city+1,c1,city+1,c3);

    for(int i=c3+1;i<=city;i++)
    dfs(dist+map[c3][i],city,c1,c2,i);
    dfs(dist+map[c3][city+1],city+1,c1,c2,city+1);
    }

    int main(){
    freopen("QQQ.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n-i;j++){
    int x;
    scanf("%d",&x);
    map[i][i+j]=map[i+j][i]=x;
    }

    dfs(0,1,1,1,1);
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2015-08-11 15:56:32

    int mymin(int x,int y){return x??y?x:y;}

    void dfs(int a,int b,int c,int s)
    {
    if(dp[a][b][c]<=s)return ;
    dp[a][b][c]=s;
    if(a==n)
    {
    ans=mymin(ans,s);
    return ;
    }
    dfs(a+1,??,??,s+map[a][a+1]);
    dfs(a+1,??,??,s+map[b][a+1]);
    dfs(a+1,??,??,s+map[c][a+1]);
    }
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    for(int j=i+1;j<=n;j++)
    {
    scanf("%d",&map[i][j]);
    }
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++)
    dp[i][j][k]=最大;
    ans=最大;
    dfs(?,?,?,?);
    printf("%d",ans);
    }

  • 0
    @ 2015-04-21 22:08:33

    我觉得无语的是,样例数据不能构成三角形,,,,,难道路不是直线是非常非常非常曲折的?

  • 0
    @ 2014-08-06 21:31:56

    else begin a[a1,a2,a3]:=min(a[a1,a2,a3],b[a3-1,a3]+dfs(a1,a2,a3-1));未考虑。。。哎

  • 0
    @ 2014-08-06 21:31:33

    发的正解
    program p1547;
    var a:array[0..101,0..101,0..101] of longint;
    n,sum,i,j:longint;
    b:array[0..101,0..101] of longint;
    c:array[1..3] of longint;
    //
    function min(a,b:longint):longint;
    begin
    if a>b then exit(b)
    else exit(a);
    end;
    //
    procedure make(a1,a2,a3:longint;var b1,b2,b3:longint);
    var k,i,j:longint;
    begin
    c[1]:=a1;c[2]:=a2;c[3]:=a3;
    for i:=1 to 3 do
    for j:=i+1 to 3 do
    if c[i]>c[j] then
    begin
    k:=c[i];c[i]:=c[j];c[j]:=k;
    end;
    b1:=c[1];b2:=c[2];b3:=c[3];
    end;
    //
    function dfs(a1,a2,a3:longint):longint;
    var i,b1,b2,b3:longint;
    begin
    if a[a1,a2,a3]<>10000000 then exit(a[a1,a2,a3]);
    if a2+1>=a3 then
    for i:=1 to a3-1 do
    begin
    make(a1,a2,i,b1,b2,b3);
    a[a1,a2,a3]:=min(a[a1,a2,a3],b[i,a3]+dfs(b1,b2,b3));
    end
    else begin
    a[a1,a2,a3]:=min(a[a1,a2,a3],b[a3-1,a3]+dfs(a1,a2,a3-1));
    end;
    for i:=1 to a2-1 do
    begin
    make(a1,i,a3,b1,b2,b3);
    a[a1,a2,a3]:=min(a[a1,a2,a3],b[i,a3]+dfs(b1,b2,b3));
    end;
    for i:=1 to a1-1 do
    begin
    make(i,a2,a3,b1,b2,b3);
    a[a1,a2,a3]:=min(a[a1,a2,a3],b[i,a3]+dfs(b1,b2,b3));
    end;
    exit(a[a1,a2,a3]);
    end;
    //
    procedure init;
    var i,j,k:longint;
    begin
    readln(n);
    for i:=1 to n-1 do
    begin
    for j:=i+1 to n do
    begin
    read(b[i,j]);b[j,i]:=b[i,j];
    end;
    readln;
    end;
    for i:=1 to n do
    for j:=1 to n do
    for k:=1 to n do a[i,j,k]:=10000000;
    a[1,1,1]:=0;
    end;
    //
    begin
    init;
    sum:=dfs(n,n,n);
    sum:=10000000;
    for i:=1 to n do
    for j:=1 to n do sum:=min(sum,a[i,j,n]);
    write(sum);
    end.

  • 0
    @ 2013-09-30 20:54:01

    有件事很恐怖——明知道自己是错的还AC了……
    附错的代码:
    uses math;
    var
    i,j,k,m,n,minx,minp,s:longint;
    c:array[1..3] of longint;
    a:array[1..100,1..100] of longint;

    begin
    readln(n); s:=0;
    fillchar(a,sizeof(a),0);
    for i:=1 to 3 do
    c[i]:=1;
    for i:=1 to n-1 do
    begin
    for j:=i+1 to n do
    begin
    read(a[i,j]);
    a[j,i]:=a[i,j];
    end;
    readln
    end;
    for i:=2 to n do
    begin
    minp:=maxlongint;
    for j:=1 to 3 do
    if minp>a[i,c[j]] then
    begin
    minp:=a[i,c[j]];
    minx:=j;
    end;
    s:=s+minp;
    c[minx]:=i;
    end;
    writeln(s)
    end.
    贪心万岁!!!

  • 0
    @ 2012-11-07 20:39:23

    ├ 测试数据 01:答案正确... (850ms, 448KB)

    ├ 测试数据 02:答案正确... (78ms, 448KB)

    ├ 测试数据 03:答案正确... (78ms, 448KB)

    ├ 测试数据 04:答案正确... (16ms, 448KB)

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

    Accepted / 100 / 1024ms / 448KB

    好吧我没用递归

  • 0
    @ 2010-04-14 19:41:21

    兄弟们,动规没有饭吃,用摸拟!!!!!!!!!!

  • 0
    @ 2010-04-14 19:38:34

    Var

    i,j,k,m,n,t:longint;

    qw:array[1..100,1..100]of longint;

    xx:array[1..3,1..2]of longint;

    Begin

    readln(n);

    for i:=1 to n-1 do

    begin

    for j:=i+1 to n do

    read(qw);

    readln;

    end;

    for i:=1 to 3 do

    begin

    xx:=1;

    xx:=0;

    end;

    for i:=2 to n do

    begin

    m:=maxlongint;

    for j:=1 to 3 do

    begin

    if xx[j,2]+qw[xx[j,1],i]

  • 0
    @ 2009-11-08 18:19:40

    不错的题。

    给个伪码:

    now:A、B、C所到达的序号最大的城市

    (我的城市编号是从0,1,2...n-1)

    a:A车的位置

    b:B车的位置

    c:C车的位置

    d[i][j]:城i和城j的距离

    ans:最佳答案,初始化为一个很大的值

    s:A、B、C车处于(a,b,c)时的最小路程

    #include "stdio.h"

    int ans

  • 0
    @ 2009-11-04 20:14:46

    每一点可以拓展最多3次,

    记录该点第I时刻所有的车数即可拓展的点.

    于是只要2维. 每次都走能拓展的最短的路

  • 0
    @ 2009-11-01 16:32:16

    奇迹般1次AC...O(n^3)的顺推法

    输入上纠结了很久

    最后敲定for i:=1 to n-1 do

    for j:=i+1 to n do

  • 0
    @ 2009-10-31 21:29:50

    我貌似也是贪心..

    冲着这70%的通过率进来的..和题目的通过率比起来..本人的通过率是多么可怜..

  • 0
    @ 2009-10-25 20:01:27

    OTZ 逆转裁判的标题

  • 0
    @ 2009-10-25 16:38:11

    果然强大..

    ...70%的通过率

信息

ID
1547
难度
1
分类
搜索 | 记忆化搜索 点击显示
标签
(无)
递交数
880
已通过
586
通过率
67%
被复制
3
上传者