Link：https://www.lydsy.com/JudgeOnline/problem.php?id=1566

 

Solution：

思路十分精奇的一道题目

 

题目要求的是$\sum_{i=1}^k a_i^2$

明显发现$a_i$是难以求解的，于是考虑如何整体处理$a_i^2$

 

由于$a_i^2=a_i*a_i$， 

因此$a_i^2$可以认为是第一人选出的方案数$a_i$乘上第二人选出的方案数$a_i$

那么只要统计两人选择相同序列的情况数即可

 

设dp[i][j][k]为取i个字符，两人在上方取到j，k个字符时相同的方案数

接下来再用滚动数组优化下转移就好了

 

Code：

//by NewErA#include 
     
       using namespace std;const int MOD=1024523; const int MAXN=510;int n,m,dp[2][MAXN][MAXN],up[MAXN],down[MAXN],t=0;char s1[MAXN],s2[MAXN]; int main(){    scanf("%d%d",&n,&m);      scanf("%s",s1);scanf("%s",s2);      for (int i=0;i
     

 

Review：

1、如果要求解某难以求解之数的多次幂时，

考虑将多次幂转化为降次的其它问题求解

（二次幂转化为两个一次问题的结果相乘）

 

2、对DP的优化：

如果为同时求解两个同样问题的DP，维护步数和即可，由$O(n^4)$降到$O(n^3)$

 

如果每次只用到上一层结果，使用滚动数组优化空间