首页 > 其他分享 >codeforces 2B B. The least round way(dp+数论)

codeforces 2B B. The least round way(dp+数论)

时间:2023-04-23 21:38:48浏览次数:48  
标签:int MAX codeforces least else 2B printf print dp


题目链接:

codeforces 2B


题目大意:

给出一个n*n的矩阵,从左上角走到右下角,只能向右或向下走,问路径上的数之积末尾0最少的方案是什么。


题目分析:

  • 首先我们要做两个预处理,处理出每个位置上的数包含多少个2的质因子和多少个5这个质因子
  • 然后我们统计路径上弄到最少的2的方案数和最少的5的方案数。
  • 这个转移方程很简单:定义dp[i][j]为走到点[i,j]时最少弄到给定质因数的个数,a[i][j]表示[i,j]位置上给定质因数的个数。
  • dp[i][j]=min(dp[i−1][j],dp[i][j−1])+a[i][j]
  • 然后我们需要证明ans=min(k,m),k代表弄到的最少的2的个数,m表示弄到的最少的5的个数。
  • 首先因为我们一定可以选择一条路径,保证这条路径上其中一个质因数的个数不超过ans,所以ans是答案的上限。
  • 然后因为我们如果能够找到两个质因数的最小值小于ans的情况时,存在一条路经能够导致kk

AC代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX 1007

using namespace std;

int n,x;
int dp[2][MAX][MAX];
int p[2][MAX][MAX];

void print ( int x , int y , int k , int f  )
{
    if ( x == 1 && y == 1 );
    else if ( x == 1 ) print ( x , y-1 , k , 0);
    else if ( y == 1 ) print ( x-1 , y , k , 1);
    else 
    {
        if ( dp[k][x][y] == dp[k][x-1][y] + p[k][x][y] )
            print ( x-1 , y , k , 1 );
        else print ( x , y-1 , k , 0);
    }
    if ( f == 3 ) return;
    printf ( "%c" , f?'D':'R' );
}

int main ( )
{
    while ( ~scanf ( "%d" , &n ) )
    {
        int flag = 0,a,b;
        for ( int i = 1 ; i <= n ; i++ )
            for ( int j = 1 ; j <= n ; j++ )
            {
                scanf ( "%d" , &x );
                if ( !x ) 
                {
                    flag = 1;
                    p[0][i][j]++;
                    p[1][i][j]++;
                    a = i , b = j;
                    continue;
                }
                while ( x%2 == 0 )
                {
                    p[0][i][j]++;
                    x /= 2;
                }
                while ( x%5 == 0 )
                {
                    p[1][i][j]++;
                    x /= 5;
                }
            }
        memset ( dp , 0x3f , sizeof ( dp ) );
        for ( int k = 0 ; k < 2 ; k++ )
            for ( int i = 1 ; i <= n ; i++ )
                for ( int j = 1 ; j <= n ; j++ )
                {
                    if ( i-1 )
                        dp[k][i][j] = min ( dp[k][i][j] , dp[k][i-1][j] );
                    if ( j-1 )
                        dp[k][i][j] = min ( dp[k][i][j] , dp[k][i][j-1] );
                    if ( i == j && i == 1 ) 
                        dp[k][i][j] = 0;
                    dp[k][i][j] +=  p[k][i][j];
                }
        int ans = min ( dp[0][n][n] , dp[1][n][n] ); 
        if ( ans > 1 && flag )
        {
            puts ( "1" );
            for ( int i = 1 ; i < a ; i++ )
                printf ( "%c" , 'D' );
            for ( int j = 1 ; j < b ; j++ )
                printf ( "%c" , 'R' );
            for ( int i = a ; i < n ; i++ )
                printf ( "%c" , 'D' );
            for ( int j = b ; j < n ; j++ )
                printf ( "%c" , 'R' );
            puts ( "" );
            continue;
        }
        printf ( "%d\n" , ans );
        if ( dp[0][n][n] < dp[1][n][n] )
            print ( n , n , 0 , 3 );
        else print ( n , n , 1 , 3 );
        puts ( "" );
    }
}


标签:int,MAX,codeforces,least,else,2B,printf,print,dp
From: https://blog.51cto.com/u_7936627/6218741

相关文章

  • codeforces 126B B. Password(kmp+dp)
    题目链接:codeforces126B题目大意:给出一个字符串,找出一个子串既是它的前缀,也是它的后缀,还是一个非后缀也非前缀的子串。题目分析:本来挺简单的一个题,最开始想复杂了,还用了后缀数组,醉了。这个题主要用的是kmp的next数组,首先我们要了解next数组的定义,next[i]表示以i为末尾的子串的后缀......
  • codeforces 118D D. Caesar's Legions(dp)
    题目链接:codeforces118D题目大意:给出n1个1,n2个2,给出k1和k2代表连续的1和2的最大长度,问能够构造的合法的不同串的数量。题目分析:能够递推,所以想到能够利用dp做。首先我们定义状态,dp[i][j][k][2]代表以1或2结尾,结尾相同的元素的数量为k,1的总数是j的当前序列长度为i的串的数量。首先......
  • codeforces 264B B. Good Sequences(dp+数论)
    题目链接:codeforces264B题目大意:给出n个数,利用这n个数构造一个好的序列,好的序列是单调增的,而且序列中相邻的两个元素都不互质,问最长的好序列的长度是多少。题目分析:首先我们定义状态dp[i]表示当前的数进行构造的序列末尾的数的质因数包含i的时候的最长的情况。然后我们从小到大枚......
  • codeforces 159D D. Palindrome pairs( manacher+dp )
    题目链接:codeforces159D题目大意:给出一个字符出,求取这个字符串中互相不覆盖的两个回文子串的对数。题目分析:首先能够用manacher模板,因为这个算法处理的字符串的长度式奇数,所以我们首先将原字符串拓展,也就是用一个没有出现过的子串填充到每两个字符之间,首位也要添加,这样处理后得到......
  • codeforces 359B B. Permutation(简单构造)
    题目链接:codeforces359B题目大意:给出n和k,要求构造一个长度为2*n的排列,满足如下的式子:∑i=1n|a2∗i−1−a2∗i|−|∑i=1na2∗i−1−a2∗i|=2∗k题目分析:首先最终构造的2*k一定是小于n的偶数,如果我们直接放入自然数的排列,结果是0,我们将2*i-1和2*i分为一组,每次调换组内位置(每组只能......
  • codeforces 505B B. Mr. Kitayuta's Colorful Graph(bfs)
    题目链接:codeforces505B题目大意:给出一个有向图,边有不同的颜色,任意给出查询,查询两点能够只通过一种颜色连通的颜色的种类数。题目分析:根据不同颜色建边,bfs即可,队列维护可用的点。AC代码:#include<iostream>#include<cstring>#include<cstdio>#include<vector>#include<alg......
  • codeforces 332B B. Maximum Absurdity(rmq)
    题目链接:codeforces332B题目大意:给出一个序列,让找出不互相覆盖的两个长度为k的段,问在两个段的权值和最大的情况下,按照左边段的左端点排序,右边段的左端点作为第二关键字排序,得到的第一个答案。题目分析:很水的数据结构的题目,我们只需要先利用前缀和预处理出所有长度为k的段的总权值......
  • codeforces 234C C. Weather(枚举+前缀后缀预处理)
    题目链接:codeforces234C题目大意:给出一个序列,问最少修改多少个元素,能保证前半截全是负数,后半截全是正数。题目分析:预处理出前缀中大于等于0的数的个数和后缀中小于等于0的数的个数。枚举每一个位置,判断以当前位置为分界点时需要修改的元素的个数。AC代码:#include<iostream>#inc......
  • codeforces 172B B. Pseudorandom Sequence Period(暴力)
    题目链接:codeforces172B题目大意:给出生成元,和递推式,求一个有限群元素的个数题目分析:暴力求取循环节即可,因为元素个数不会超过mod的大小,所以暴力法复杂度仅仅是O(105)AC代码:#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cstdio>#de......
  • codeforces 368B B. Sereja and Suffixes(树状数组)
    题目链接:codeforces368B题目大意:给出一个长度为n的序列a,给出m个查询l,对于每个查询输出[l,n]的区间内不同数的个数。题目分析:将查询按照l的大小排序,从大到小的遍历,每次将>=当前l的位置的a[i]全部加入树状数组,树状数组记录每个数是否出现过。每次结果就是查询树状数组的总和,要保证......