首页 > 代码库 > codeforces2B - The least round way DP

codeforces2B - The least round way DP

2024-07-15 11:27:42   220人阅读

题意：给你一个矩阵，问你从左上角走一直走到右下角只能向右向下，问你最后乘起来尾数0个数最少的数值和路径是什么

解题思路：可以知道 要么这条路径上和 的质因子  2 的个数 < 5的个数， 要么 5的个数 < 2 的个数，所以就在一个节点里面添加两个信息，一种是2最小 ，一种是5最小，

最开始没注意看数据  莫名 RE 31组数据，然后发现有0,这里特判一下就行了，写了200行也是给自己跪了。

解题代码：

  1 // File Name: 2b.cpp  2 // Author: darkdream  3 // Created Time: 2014年08月02日 星期六 15时17分39秒  4   5 #pragma comment(linker, "/STACK:102400000,102400000")  6 #include<vector>  7 #include<list>  8 #include<map>  9 #include<set> 10 #include<deque> 11 #include<stack> 12 #include<bitset> 13 #include<algorithm> 14 #include<functional> 15 #include<numeric> 16 #include<utility> 17 #include<sstream> 18 #include<iostream> 19 #include<iomanip> 20 #include<cstdio> 21 #include<cmath> 22 #include<cstdlib> 23 #include<cstring> 24 #include<ctime> 25 #pragma comment(linker, "/STACK:102400000,102400000") 26 #define LL long long 27 using namespace std; 28 #pragma comment(linker, "/STACK:102400000,102400000") 29  30 struct node2{ 31     LL n2 ;  32     LL n5 ; 33     bool d; 34 }; 35 struct node{ 36    node2 m[2];  37 }dp[1004][1004]; 38 LL l2[100]; 39 LL l5[100]; 40 int nl2; 41 int nl5; 42 void init() 43 { 44    memset(dp,0,sizeof(dp)); 45    l2[1] = 2;  46    l5[1] = 5; 47    for(int i = 2;;i ++) 48    { 49       l2[i] = l2[i-1]*2; 50       if(l2[i] > 1e9) 51       { 52          nl2 = i ;  53          break; 54       } 55    } 56    for(int i = 2;;i ++) 57    { 58       l5[i] = l5[i-1]*5; 59       if(l5[i] > 1e9) 60       { 61          nl5 = i ;  62          break; 63       } 64    } 65 } 66 void solve(int x,int y ,LL t) 67 { 68     int t2 ;  69     int t5 ; 70     for(int i =1 ;;i ++) 71     { 72        if(t % l2[i] != 0 ) 73        { 74            t2 = i-1; 75            break; 76        } 77     } 78     for(int i =1 ;;i ++) 79     { 80        if(t % l5[i] != 0 ) 81        { 82            t5 = i-1; 83            break; 84        } 85     } 86     dp[x][y].m[0].n2 = t2; 87     dp[x][y].m[0].n5 = t5; 88     dp[x][y].m[1] = dp[x][y].m[0]; 89 } 90 int num; 91 bool ans[2000004] = {0}; 92 bool d; 93 void findway(int x, int y ) 94 { 95     num --; 96     if((x == 1 && y == 1)) 97         return; 98      99     if(dp[x][y].m[d].d)100     {101       ans[num] = 1;102       findway(x,y-1);103       return;104     }else{105       findway(x-1,y);106       return;107     }108 }109 void dp_clear(int x, int y)110 {111     dp[x][y].m[0].n2 = 1e9;112     dp[x][y].m[0].n5 = 1e9;113     dp[x][y].m[0].d = 0;114     dp[x][y].m[1] = dp[x][y].m[0];115 }116 LL a[1005][1005];117 int main(){118    int n ;119    init();120    scanf("%d",&n);121    num = 2*n-1;122    int ok = 0;123    int x, y;124    for(int i = 1;i <= n;i ++)125        for(int j = 1;j <= n ;j ++ )126        {127 128           LL temp ; 129           scanf("%I64d",&a[i][j]);130           if(a[i][j] != 0 )131             solve(i,j,a[i][j]);132           else{133             ok = 1;134             x = i; 135             y = j;136           }137        }138    for(int i = 2;i <= n;i ++)139    {140       dp[1][i].m[0].n2 = dp[1][i-1].m[0].n2 + dp[1][i].m[0].n2;141       dp[1][i].m[0].n5 = dp[1][i-1].m[0].n5 + dp[1][i].m[0].n5;142       dp[1][i].m[0].d = 1; 143       dp[1][i].m[1] = dp[1][i].m[0]; 144    }145    for(int i = 2;i <= n;i ++)146    {147       dp[i][1].m[0].n2 = dp[i-1][1].m[0].n2 + dp[i][1].m[0].n2;148       dp[i][1].m[0].n5 = dp[i-1][1].m[0].n5 + dp[i][1].m[0].n5;149       dp[i][1].m[1] = dp[i][1].m[0]; 150    }151    for(int i =2;i <= n;i ++)152        for(int j = 2;j <= n;j ++)153        {154            if(a[i][j] == 0 )155            {156              dp_clear(i,j);157              continue;158            }159            if(dp[i-1][j].m[0].n2 < dp[i][j-1].m[0].n2)160            {161                dp[i][j].m[0].n2 += dp[i-1][j].m[0].n2;162                dp[i][j].m[0].n5 += dp[i-1][j].m[0].n5;163            }else{164                dp[i][j].m[0].n2 += dp[i][j-1].m[0].n2;165                dp[i][j].m[0].n5 += dp[i][j-1].m[0].n5;166                dp[i][j].m[0].d = 1; 167            }168            if(dp[i-1][j].m[1].n5 < dp[i][j-1].m[1].n5)169            {170                dp[i][j].m[1].n2 += dp[i-1][j].m[1].n2;171                dp[i][j].m[1].n5 += dp[i-1][j].m[1].n5;172            }else{173                dp[i][j].m[1].n2 += dp[i][j-1].m[1].n2;174                dp[i][j].m[1].n5 += dp[i][j-1].m[1].n5;175                dp[i][j].m[1].d = 1; 176            }177        }178    LL T = min(min(dp[n][n].m[0].n2,dp[n][n].m[0].n5),min(dp[n][n].m[1].n2,dp[n][n].m[1].n5));179    if(ok)180    {181       if(T!= 0 )182       {183         printf("1\n");184         for(int i = 1;i < x;i ++)185             printf("D");186         for(int i = 1;i < n;i ++)187             printf("R");188         for(int i = x+1;i <=n;i ++)189             printf("D");190         printf("\n");191         return 0 ; 192       }193    }194    printf("%I64d\n",T);195    d = 0; 196    if(min(dp[n][n].m[0].n2,dp[n][n].m[0].n5) > min(dp[n][n].m[1].n2,dp[n][n].m[1].n5))197    { 198        d = 1;199        findway(n,n);200    }201    else findway(n,n);202    for(int i = 1;i <= 2*n-2;i++)203        if(ans[i])204            printf("R");205        else printf("D");206    printf("\n");207 return 0;208 }
View Code

 


联系
我们