hihocoder offer收割编程练习赛8 C 数组分拆

思路：（引自bfsoyc的回答：http://hihocoder.com/discuss/question/4160）

动态规划。状态dp[i]表示前i个数的合法的方案数，转移是

dp[i] = sum{ dp[k] | 1 < k < i && sum(k+1,i)!=0 }

= sum{ dp[k] | 1 < k < i } - sum{ dp[k] | 1 < k < i && sum(k+1,i)==0 }

关键是求后半部分怎么找到sum(k+1,i)==0 的k，等价于找 prefixSum(k)== prefixSum(i)，因为这里前缀比后缀维护容易。利用容器map M, M[ps] = sum{dp[k] | prefixSum(k)==ps }。那么 dp[i] = sum{ dp[k] | 1 < k < i } - M[prefixSum(i)]。

实现：

 #include <iostream>

 #include <cstdio>

 #include <map>

 using namespace std;

 const int mod = 1e9 + ;

 int a[], s[], dp[], n, total;

 map<int, int> g;

 int solve()

 {

     total = dp[] = ;

     g[] = ;

     for (int i = ; i <= n; i++)

     {

         if (!g.count(s[i]))

             g[s[i]] = ;

         dp[i] = ((total - g[s[i]]) % mod + mod) % mod;

         g[s[i]] = (g[s[i]] + dp[i]) % mod;

         total = (total + dp[i]) % mod;

     }

     return dp[n];

 }

 int main()

 {

     cin >> n;

     for (int i = ; i <= n; i++)

     {

         scanf("%d", &a[i]);

         s[i] = s[i - ] + a[i];

     }

     cout << solve() << endl;

     return ;

 }

巴特西

hihocoder offer收割编程练习赛8 C 数组分拆

最新文章

热门文章