CodeForces - 466C Number of Ways(推公式/dp)

题目链接：点击查看

题目大意：给出一个长度为 n 的数列，现在要求出满足条件的 ( i , j ) 的匹配数量，满足：

题目分析：训练时推的公式，简单说一下吧，维护前缀和 sum，则确定两个断点 ( i , j ) 后可以确定下来三个区间：

sum[ i - 1 ]

sum[ j ] - sum[ i - 1 ]

sum[ n ] - sum[ j ]

因为需要三段区间的权值和连等，根据等式的传递性，我们可以让前两项相等，再让后两项相等，最后不难推出三项连等，建立等式：

前两项相等：sum[ i - 1 ] = sum[ j ] - sum[ i - 1 ]，推得 2 * sum[ j ] = sum[ i - 1 ] * 4（两侧同时乘以 2，下面要用）

后两项相等：sum[ j ] - sum[ i - 1 ] = sum[ n ] - sum[ j ]，推得 2 * sum[ j ] = sum[ n ] + sum[ i - 1 ]

利用 2 * sum[ j ] 当做中间量，不难看出当确定下来 i 后，只有满足 sum[ n ] + sum[ i - 1 ] = sum[ i - 1 ] * 4 时才存在 j 与其匹配，此时只需要查找一下区间 [ i , n ] 中有多少个 j 与其匹配即可

---

另一种方法，是将其转换成一个很经典的 dp 模型，这里拿一下 PTA 乙级题目的题面：

字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位(P)，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位(P)，第 4 位(A)，第 6 位(T)。

现给定字符串，问一共可以形成多少个 PAT？

比较显然的是，假设 sum 为 n 个数之和，( i , j ) 将整个序列分成的三段大小分别都是 sum / 3（设 sum % 3 == 0），所以第一个断点的位置也就是前缀和等于 sum / 3 的位置，同理第二个断点的位置也就是前缀和等于 sum / 3 * 2 的位置，如此一来就转换成了上面那个非常经典的动态规划模型：

给定 n 个位置，问一共可以形成多少个 ( sum/3 的位置，sum/3*2 的位置)

如此一来这个题目就可以继续扩展了，诸如匹配 ( i , j , k ) 三元对的断点将数列四等分划分这样的

妙啊

代码：
推公式

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;LL sum[N];map<LL,int>mp;int main() { #ifndef ONLINE_JUDGE // freopen("data.ans.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){LL num;scanf("%lld",&num);sum[i]=sum[i-1]+num;}LL ans=0;for(int i=n-1;i>1;i--)//枚举i {mp[sum[i]*2]++;if(4*sum[i-1]==sum[n]+sum[i-1]) ans+=mp[sum[n]+sum[i-1]];}printf("%lld\n",ans);return 0; }

dp

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;LL sum[N],dp[N][2];int main() { #ifndef ONLINE_JUDGE // freopen("data.ans.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){LL num;scanf("%lld",&num);sum[i]=sum[i-1]+num;}if(sum[n]%3!=0)return 0*puts("0");LL mark=sum[n]/3;for(int i=1;i<=n;i++){for(int j=0;j<2;j++)dp[i][j]=dp[i-1][j];if(i!=n){if(sum[i]==mark)dp[i][0]++;if(sum[i]==mark*2)dp[i][1]+=dp[i-1][0];}}printf("%lld\n",dp[n][1]);return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 466C Number of Ways(推公式/dp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。