当前位置: 代码迷 >> 综合 >> 51nod 子序列的个数 (动规分析方法)
  详细解决方案

51nod 子序列的个数 (动规分析方法)

热度:63   发布时间:2023-09-20 19:59:07.0

这道题的分析方法我很需要学习学习。

一开始我想的是f[i][j]表示前i个数子序列长度为j的个数

然后发现新加入一个数的时候会和前面的重复,这个时候不知道该怎么处理这种重复。

其实我再继续往下想就可以想到,这些重复的序列都有一个特征,结尾都是新加入的这个数

那么这就启示我们可以利用前面算出的结果来算出这个值而舍去

 

然后题解的分析是这样。

先考虑暴力该怎么做,然后再想怎么优化

暴力的话显然是枚举每一位去或者不取,然后去重复。不算去重的话时间复杂度为2^n

然后我们尝试用动态的思想来优化,最后的答案可以从前面的哪个状态推过来?

我们看最后一位取或者不取,前面是2^(n-1),这一位取或者不取两种情况,乘以2

就是2^n

那么我们可以尝试设一下f[i]表示前i项子序列的长度

那么有f[i] = f[i-1] * 2

但是很显然怎么去重复是个很大的问题。

重复的子序列的结尾一定是当前的这个数

那么以当前这个数为结尾的子序列为多少呢?

根据定义可以得知为f[j-1],j为前i-1项里面当前项a[i]最后一次出现的位置

因为j前面的所有子序列加上一个j就是以当前这个数为结尾的个数

如果j不存在,那么就不用减去。

要注意这里j是最后一个,因为后面的位置包含了前面的位置的结果。

最后要注意f[0] = 1,这样方便我们来更新值,同时最后输出答案的时候减去1

 

以后学习动规的时候看题解一定要看是怎么推出来的,自己为什么没想到

#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112345;
const int MOD = 1e9 + 7; 
int a[MAXN], f[MAXN], path[MAXN], n;int main()
{scanf("%d", &n);REP(i, 1, n + 1) scanf("%d", &a[i]);f[0] = 1;REP(i, 1, n + 1){f[i] = (f[i-1] << 1) % MOD;if(path[a[i]] > 0) f[i] = (f[i] - f[path[a[i]] - 1] + MOD) % MOD;path[a[i]] = i;}printf("%d\n", f[n] - 1);return 0;	
}