Codeforces 1005D Polycarp and Div 3

---

dp[i]表示前i個(gè)數(shù)最多能分成多少塊%3為0，nxt[x]表示x這個(gè)上一次出現(xiàn)的位置。
首先想到 $ dp[i] = max(dp[j]) + 1, (sum[i]-sum[j]) mod 3 == 0$，然后注意到他一定是從最近的那個(gè)滿足條件的位置，也就是nxt[i]轉(zhuǎn)移過來(lái)的，因?yàn)橄啾戎暗奈恢眠@樣一定不會(huì)更糟，所以方程就是 $ dp[i] = max( dp[nxt[i]] + 1, dp[i-1]) $
還有一個(gè)點(diǎn)就是如果當(dāng)前位置模3為0，那么dp[i]一定大于1，忘了這個(gè)轉(zhuǎn)移結(jié)果一致直WA，早點(diǎn)拍就好了。

#include <bits/stdc++.h> #define pb push_back const long double PI = acos(-1.0); const long double eps = 0.000001; using namespace std; int n,m,nxt[5],dp[222222]; char s[222222]; //174094882455171152761423221685761 int main() {scanf(" %s",s);n = strlen(s);memset(nxt,-1,sizeof(nxt));int sum = 0;dp[0]=((s[0]-'0')%3==0);sum += (s[0]-'0');sum%=3;nxt[sum]=0;for(int i = 1; i < n; ++i) {int x = s[i] - '0';sum = (sum + x)%3;dp[i] = dp[i-1];if(sum==0)dp[i]=max(dp[i],1);if(nxt[sum]!=-1) dp[i] = max(dp[nxt[sum]] + 1,dp[i]);nxt[sum]=i;}printf("%d\n",dp[n-1]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/RRRR-wys/p/9286901.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 1005D Polycarp and Div 3的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。