UVA 12385

-——————————————————————————————————————————————————

题目描述：

这题意看了好多遍都没有看懂。英语不过关啊。

要求找出不冲突的 “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

#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;
}