CodeForces 1005D Polycarp and Div 3（思维、贪心、dp）

http://codeforces.com/problemset/problem/1005/D

题意：

给一个仅包含数字的字符串，将字符串分割成多个片段（无前导0），求这些片段里最多有多少是3的倍数

思路一（贪心）：

from：https://blog.csdn.net/islittlehappy/article/details/81006849

一个数是3的倍数，则各位的和能被3整除。

对于单独的一个数字，如果是3的倍数，则ans++

否则，考虑连续的两个数字，如果是，则ans++

如果第三个数本身是3的倍数，则ans++

如果第三个数不是3的倍数，则对于前两个数的和对3取余，结果为[1,1]或者[2,2]（如果为[1,2],[2,1]，则这两个数字能够被3整除）

对于第三个数对3取余，结果为0,1,2

0：第三个数本身能被3整除ans++

1：[1,1,1]是3的倍数取全部，[2,2,1]取后两个 ans++

2：[1,1,2]取后两个 [2,2,2]是3的倍数，取全部 ans++

所以对于n=3 一定可以找到

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int maxn = 2e5+;

 char str[maxn];

 int main()

 {

     scanf("%s",str);

     int t=,sum=,ans=,n=;

     for(int i=;i<strlen(str);i++)

     {

         t=(str[i]-'')%;

         sum+=t;

         n++;

         if(t==||sum%==||n==)

         {

             ans++;

             n=sum=;

         }

     }

     printf("%d\n",ans);

     return ;

 }

思路二（dp）：

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <math.h>

 #include <algorithm>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <sstream>

 const int INF=0x3f3f3f3f;

 typedef long long LL;

 const int mod=1e9+;

 //const double PI=acos(-1);

 #define Bug cout<<"---------------------"<<endl

 const int maxm=1e6+;

 const int maxn=1e6+;

 using namespace std;

 char str[maxn];

 LL sum[maxn];//前缀和

 int dp[maxn];//dp[i]表示前i个数的答案 

 int main()

 {

     scanf("%s",str+);

     for(int i=;str[i];i++)

     {

         if(i==)

             sum[i]=str[i]-'';

         else

             sum[i]=sum[i-]+str[i]-'';

     }

     int num=;

     if((str[]-'')%==)

         dp[]=;

     for(int i=;str[i];i++)

     {

         if((str[i]-'')%==)

             dp[i]=dp[i-]+;

         else

         {

             for(int j=i-;j>;j--)

             {

                 if((sum[i]-sum[j-])%==)

                 {

                     dp[i]=max(dp[i],dp[j-]+);

                     break;

                 }

                 else

                     dp[i]=dp[i-];

             }

         }

     }

     printf("%d\n",dp[strlen(str+)]);

     return ;

 }

巴特西

CodeForces 1005D Polycarp and Div 3（思维、贪心、dp）

最新文章

热门文章