河南省第六届ACM程序设计大赛-白红宇

河南省第六届ACM程序设计大赛

阅读量：5077 次

发布时间：2019-06-12

本文共 4516 字，大约阅读时间需要 15 分钟。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define INF 20000000 struct point{    int x, y, v;}; point node[5005];int fa[505]; bool cmp(point a, point b){    return a.v < b.v;//边从小到大}int find(int n){    return n == fa[n] ? n : fa[n] = find(fa[n]);}int gcd(int a, int b){    return b ? gcd(b, a%b) : a;}int main(){    int i, j, t, e;    int start, end, row, edge, maxv, minv;    double radio;    cin>>t;    while(t--)    {        cin>>row>>edge;        for(i = 1; i <= edge; i++)        {            cin>>node[i].x>>node[i].y>>node[i].v;        }        cin>>start>>end;        sort(node + 1, node+edge + 1, cmp);        radio = INF;        for(e = edge; e > 0; e--) //从最大的边开始，将比它小的边加入        {            for(i =1; i <= row; i++)                fa[i] = i;            for(i = e; i > 0; i--)            {                int a = find(node[i].x);                int b = find(node[i].y);                if(a == b)                    continue;                else                    fa[a] = b;                if(find(start) == find(end))                    break;//起点和终点在都一个集合里            }            if(i == 0)                break;//如果把边都加进去完了，说明起点和终点不连通            if(node[e].v/(node[i].v*1.0) < radio)            {                radio = node[e].v / (node[i].v * 1.0);                maxv = node[e].v;                minv = node[i].v;            }        }        int g = gcd(maxv, minv);        if(radio == INF)            printf("IMPOSSIBLE\n");        else if(maxv % minv == 0)            printf("%d\n", maxv / minv);        else            printf("%d/%d\n", maxv/g, minv/g);    }    return 0;}

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef unsigned long long LL; #define N 110#define met(a,b) (memset(a,b,sizeof(a)))#define max4(a,b,c,d) (max(max(a,b),max(c,d)))  int a[N][N], dp[N*2][N][N]; int main(){    int n, m, T;     scanf("%d", &T);     while(T--)    {        int i, j, k;         met(a, 0);        met(dp, 0);         scanf("%d%d", &n, &m);         for(i=1; i<=n; i++)        for(j=1; j<=m; j++)            scanf("%d", &a[i][j]);         dp[0][1][1] = a[1][1];        for(k=1; k<=n+m-2; k++)        {            for(i=1; i<=n; i++) ///i 代表第一个人所在的行            for(j=1; j<=n; j++) ///j 代表第二个人所在的行                        {                   dp[k][i][j] = max4(dp[k-1][i][j], dp[k-1][i][j-1], dp[k-1][i-1][j], dp[k-1][i-1][j-1]);                if(i!=j)                    dp[k][i][j] += a[i][k+2-i] + a[j][k+2-j];                else                     dp[k][i][j] += a[i][k+2-i];            }        }         printf("%d\n", dp[n+m-2][n][n]);    }    return 0;}

View Code

G:

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef unsigned long long LL;#define N 110#define met(a,b) (memset(a,b,sizeof(a)))#define max4(a,b,c,d) (max(max(a,b),max(c,d)))LL dp[N][N][3];///dp[i][j][0] i位数，fun[i]为j的最后一位为0///dp[i][j][1] i位数，fun[i]为j的最后一位为1///dp[i][j][1] dp[i][j][0]与dp[i][j][1]之和int main(){    int T, i, j;    dp[0][0][0] = dp[0][0][2] = 1;    dp[1][0][0] = dp[1][0][1] = 1;    dp[1][0][2] = 2;    for(i=2; i
          
           =1) dp[i][j][1] += dp[i-1][j-1][1];            dp[i][j][2] = dp[i][j][0] + dp[i][j][1];        }    }    scanf("%d", &T);    while(T--)    {       int n, m;       scanf("%d%d", &n, &m);       printf("%lld\n", dp[n][m][2]);    }    return 0;}

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef unsigned long long LL;#define INF 0x3f3f3f3f#define N 1100#define met(a,b) (memset(a,b,sizeof(a)))#define max4(a,b,c,d) (max(max(a,b),max(c,d)))int a[N], dp[N];///dp[i]代表i个羊一起过河需要花费的最短时间int main(){    int T;    scanf("%d", &T);    while(T--)    {        int n, m, i, j;        scanf("%d%d", &n, &m);        for(i=1; i<=n; i++)            scanf("%d", &a[i]);        dp[1] = a[1] + m;        for(i=2; i<=n; i++)            dp[i] = dp[i-1]+a[i];        dp[0] = 0;        for(i=1; i<=n; i++)        {            for(j=i; j<=n; j++)            {               dp[j] = min(dp[j], dp[j-i]+dp[i]+m);            }        }        printf("%d\n", dp[n]);    }    return 0;}