本质上升子序列的数量
作者:
cxyjq
,
2024-04-07 23:33:46
,
所有人可见
,
阅读 10
本质上升的数量
一开始暴力写的出不来,看题解知道可以用dp,dp[i]表示以下标为i的字符为结尾的上升子序列。
i -> 1 ~ N - 1,j -> 0 ~ i;(1)如果s[i] > s[j],dp[i] += dp[j],表示以j为结尾的也可以由i结尾,(2)如果s[i] == s[j], dp[i] -= dp[j],表示减去i位置与j位置重复的上升子序列,即不重复累加本质相同的上升子序列
#include<bits/stdc++.h>
using namespace std;
const int N = 200;
int dp[N];
string s = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
long long ans = 0;
int main()
{
for (int i = 0; i < N; i++)dp[i] = 1;
for (int i = 1; i < N; i++)
for (int j = 0; j < i; j++)
if (s[i] > s[j])
dp[i] += dp[j];
else if(s[i] == s[j])
dp[i] -= dp[j];
for (int i = 0; i < N; i++)ans += dp[i];
cout << ans << '\n';
return 0;
}