做网站用什么域名好,网站建设的淘宝模板,营销外包团队怎么收费,青岛网站开发企业题目链接 分析#xff1a; 最近做的区间dp挺多 最简单的#xff1a;n^3枚举#xff0c;显然TLE 其实有一个很显然的dp状态#xff1a; f[i][j]表示结尾是i#xff0c;j的等差数列的数量#xff1a; f[i][j]Σ(f[k][j]1) (a[i]-a[j]a[j]-a[k]) 但是这样的复杂度也是… 题目链接 分析 最近做的区间dp挺多 最简单的n^3枚举显然TLE 其实有一个很显然的dp状态 f[i][j]表示结尾是ij的等差数列的数量 f[i][j]Σ(f[k][j]1) (a[i]-a[j]a[j]-a[k]) 但是这样的复杂度也是n^3 这是我们要注意到题目中a[i]的范围只有-500 那我们就可以设计状态 f[i][j]表示结尾是i公差是j的等差数列的个数 然而真正的转移方程长这样 f[i][a[i]-a[j]]Σ(f[j][a[i]-a[j]]1) 这样可以同时保证公差一定是序列中存在的而且复杂度为n^2 //1是i和j组成的一个等差数列 最后的答案要加上n tip 这道题的转移较为新颖没有直接枚举公差而是枚举最后两个数 但是状态的转移还是根据公差 这样就可以直接把dp降下一维了 c的下标从0开始这是需要特别注意的一点 从此题可以看出 某一类具有一定阶段性的计数题目也可以用dp来解决 这里写代码片
#includecstdio
#includeiostream
#includecstringusing namespace std;const int mod9901;
const int N1010;
int n;
int a[N],f[N][N*3],ans0,mx,mn;void doit()
{int i,j,k;memset(f,0,sizeof(f));for (i2;in;i) //长度为一的我们在dp中不算 for (j1;ji;j) //{f[i][a[i]-a[j]1000]f[j][a[i]-a[j]1000]1;f[i][a[i]-a[j]1000]%mod;}ansn;for (i1;in;i)for (j0;j3000;j) ansf[i][j],ans%mod;
}int main()
{scanf(%d,n);for (int i1;in;i) scanf(%d,a[i]);doit();printf(%d,ans);return 0;
}转载于:https://www.cnblogs.com/wutongtong3117/p/7673272.html
