关键
DP,直接枚举当前这个位置的数可能的值,然后就可以递推出下一个位置可能的值,直接相加或者减去就可以了。
因为当前的这个值可能是负数,所以需要加上一个偏移
PS:其实我又理解错题目了。但是感觉这个DP推着还是很有感觉的,感觉难度还行,就是我菜了
代码
//知识点:1.偏移量 2.DP只看关键位置就可以了
#include <bits/stdc++.h>
using namespace std;
const int M=310,N=300*300;
const int mod=998244353;
int a[M];
int f[M][M*M*2];
void add(int &x,int y) {
x=(x+y)%mod;
}
//首先是题目理解错了
//我以为是要构造
//再就是有一个偏移量
signed main() {
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
f[2][a[2]+N]=1;
//当前这个数,和下一个是什么就行了,上一个是什么不重要,反正会变得不一样
for(int i=2;i<n;i++) {
for(int j=-N;j<=N;j++) {
if(j) {
add(f[i+1][a[i+1]-j+N],f[i][j+N]);//进行偏移
add(f[i+1][a[i+1]+j+N],f[i][j+N]);
}
else add(f[i+1][a[i+1]+N],f[i][j+N]);
}
}
int ans=0;
for(int i=-N;i<=N;i++)
add(ans,f[n][i+N]);//统计答案
cout<<ans<<endl;
return 0;
}
//执行完成n-2次操作后,会有多少个不同的数组
//好像题目又理解错了
标签:const,--,300,CF,edu141,int,DP
From: https://www.cnblogs.com/basicecho/p/17036521.html