题目链接：https://codeforces.com/contest/1783/problem/D
大致题意： 给你一个长度为n的数组a，你必须要进行n-2次操作，对于下标i（在2-（n-1）之间），
在每次操作中，你可以将a[i-1] = a[i-1]+a[i],a[i+1] = a[i+1]-a[i];
也可以将a[i-1] = a[i-1]-a[i],a[i+1] = a[i+1]-a[i];
问你，在进行n-2次操作后，数组会出现多少种不同的情况；
解题思路： 我们观察，可以发现，如果a[i] == 0，那么不论进行什么操作，前后的数是不会发生变化的；
但是，如果a[i]!=0，那么这俩次操作的结果是不同的，这是因为：
a【i-1】会因为a【i】不为0，从而有不同的结果，于是最后的数组也会不相同；
观察到这点后，我们开始思考要采取什么方法去写这题；
对于这类计数类的题目，大致可以分为贪心，动态规划，数学排列组合这几种方法解题；
而这题，显然贪心是解决不了的，用排列组合的话，需要考虑 i 位置上会有多少种为0的结果，也不好想；
那么现在就只有动态规划可以尝试一下；
我们思考怎么构造这个转移方程；
已知 i-1位置为 k 的情况有dp【i-1】【k】种，那么考虑 i 位置的情况，（nums【i】为i位置一开始的数）；
如果 nums【i】 = nums【i】 + k，那么dp【i】【nums【i】+k】+=dp【i-1】【k】；
如果nums【i】 = nums【i】 - k，那么dp【i】【nums【i】-k】 +=dp【i-1】【k】；
然后我们观察到，数组一开始的每个数的范围是小于300，那么k的范围只会在 -90000 到 90000之间；
然后n的范围是300，那么O（n^3)大致为27000000，差不多就是3e7左右，发现是可行的；
那么我们只需要对于每个i，我们枚举k就行了；
需要注意的是，当k为0的时候，我们只需要转移一次就行了；
时间复杂度：O（n^3)
ac代码：
#include<bits/stdc++.h>
const int N = 306;
const int mod = 998244353;
int nums[N], dp[N][2 * N * N], mx = 90000;
int main()
{
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
int n; std::cin >> n;
for (int i = 1; i <= n; ++i)std::cin >> nums[i];
dp[2][nums[2] + mx] = 1;
for (int i = 3; i <= n; ++i)for (int k = -mx; k <= mx; ++k)
{
dp[i][nums[i]+k+mx] = (dp[i][nums[i]+k+mx]+dp[i-1][k+mx])%mod;
if(k)dp[i][nums[i]-k+mx] = (dp[i][nums[i]-k+mx]+dp[i-1][k+mx])%mod;
}
int ans = 0;
for (int k = 0; k <= 2 * mx; ++k)ans = (ans + dp[n][k]) % mod;
std::cout << ans << "\n";
return 0;
}
这题，注意到数组的大小以及每个初始数的大小的话，其实还是很好想到这种方法的；所以说，数据范围得看好（乐
标签：std,Educational,Rated,nums,int,141,那么,数组,dp From： https://www.cnblogs.com/ACMER-XiCen/p/17104910.html