-——————————————————————————————————————————————————
題目描述：
這題意看了好多遍都沒有看懂。英語不過關啊。
要求找出不沖突的 “interesting” 子序列。
——————————————————————————————————————————————————
題目解答：
用dp做即可。標記前一次出現 s[i] 的位置，若還未出現過，記為0。
dp[i] = max(dp[i-1], dp[last[s[i]]] + 1); 同時更新last[s[i]]。
這樣做正確性：因為題目舉不沖突的串，本方法將忽略 i 與 last[s[i]] 之間的各種串。若下一次選擇 i 與 last[s[i]] 之間的某一數做起點，那顯然 s[i] 結尾的串就被忽略了。另外，若有 123121 這種重疊串，我們顯然會選擇將這個重疊串分開，所以更新last時只更新最後一次遇到的s[i]就可以了。
——————————————————————————————————————————————————
源代碼：
[cpp]
#include<stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
int main()
{
int t = 0,n = 0;
int s[100010];
int i = 0;
int dp[100010],last[100010];
int ans = 0;
scanf("%d",&t);
while((t--)>0)
{
scanf("%d",&n);
ans = 0;
for(i = 1;i<=n;i++)
{
scanf("%d",&s[i]);
last[s[i]] = 0;
}
last[s[1]] = 1;
dp[1] = 0;
for(i = 2;i<=n;i++)
{
if(last[s[i]] != 0)
dp[i] = max(dp[i-1],dp[last[s[i]]]+1);
else
dp[i] = dp[i-1];
last[s[i]] = i;
ans = max(dp[i],ans);
}
printf("%d\n",ans);
}
return 0;
}
