【dp】codeforces C. Vladik and Memorable Trip

http://codeforces.com/contest/811/problem/C

【题意】

给定一个自然数序列，在这个序列中找出几个不相交段，使得每个段的异或值之和相加最大。

段的异或值这样定义：段中每个不同数字（不重复）相异或。

段有这样的要求：段中任意一个数字不会在段外出现。

【思路】

首先预处理每个数字第一次出现和最后一次出现的位置，这样对于一个区间[l,r]就很容易判断是否为满足题意的段。

然后区间DP，dp[i]表示子序列[1,i]的最大值。

状态转移：对于dp[i]，最小值为dp[i-1],即a[i]在任意段外；如果a[i]的最后一次出现位置大于i,那么没有更新的余地；否则，可能找到这样的l,S.T.dp[i]=max(dp[i],dp[l-1]+sum[l,i])。

如何找到这样的l?

首先可以肯定的是l最小为first[a[i]],然后遍历[first[a[i]],last[a[i]]]中的每个数，不断更新l=min(l,first[a[k]])。

那么为什么dp[i]不可能是dp[j]+sum[j-1,i](j<l)?

因为这样的j一定不满足[j,i]是一个满足题意的段.

如果last[a[j]]<last[a[i]],那么刚刚在遍历[first[a[i]],last[a[i]]]的时候应该已经找到j,即j>=l,矛盾

如果last[a[j]]>last[a[i]],这样的段也不满足题意。

【TLE】

 #include <iostream>

 #include <stdio.h>

 #include <cmath>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <string>

 #include <bitset>

 #include <ctime>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int n;

 const int maxn=;

 int a[maxn];

 int fir[maxn];

 int last[maxn];

 int dp[maxn];

 int check(int l,int r)

 {

     int vis[maxn];

     memset(vis,,sizeof(vis));

     for(int i=l;i<=r;i++)

     {

         if(last[a[i]]>r||fir[a[i]]<l)

         {

             return -;

         }

     }

     int x=;

     for(int i=l;i<=r;i++)

     {

         if(!vis[a[i]])

         {

             x^=a[i];

             vis[a[i]]=;

         }

     }

     return x;

 }

 int main()

 {

     while(~scanf("%d",&n))

     {

         memset(dp,,sizeof(dp));

         memset(fir,,sizeof(fir));

         memset(last,,sizeof(last));

         for(int i=;i<=n;i++)

         {

             scanf("%d",&a[i]);

             if(!fir[a[i]])

             {

                 fir[a[i]]=i;

              }

              last[a[i]]=i;

         }

         for(int i=;i<=n;i++)

         {

         //    cout<<fir[a[i]]<<" "<<last[a[i]]<<endl;

         }

         for(int i=;i<=n;i++)

         {

             dp[i]=dp[i-];

             for(int k=;k<=i;k++)

             {

                 int num=check(k,i);

                 if(num>)

                 {

                     dp[i]=max(dp[i],dp[k-]+num);

                 }

             }

         //    printf("dp[%d]=%d\n",i,dp[i]);

         }

         cout<<dp[n]<<endl;

     }

     return ;

 }

一开始没想到怎样找l的方法，直接枚举,时间复杂度O(n^3)（1^2+2^2+.....+n^2=n(n+1)(2n+1)/6）

【Accepted】

 #include <iostream>

 #include <stdio.h>

 #include <cmath>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <string>

 #include <bitset>

 #include <ctime>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int n;

 const int maxn=;

 int a[maxn];

 int fir[maxn];

 int last[maxn];

 int dp[maxn];

 int sum(int l,int r)

 {

     int vis[maxn];

     memset(vis,,sizeof(vis));

     int x=;

     for(int i=l;i<=r;i++)

     {

         if(!vis[a[i]])

         {

             x^=a[i];

             vis[a[i]]=;

         }

     }

     return x;

 }

 int main()

 {

     while(~scanf("%d",&n))

     {

         memset(dp,,sizeof(dp));

         memset(fir,,sizeof(fir));

         memset(last,,sizeof(last));

         for(int i=;i<=n;i++)

         {

             scanf("%d",&a[i]);

             if(!fir[a[i]])

             {

                 fir[a[i]]=i;

              }

              last[a[i]]=i;

         }

         for(int i=;i<=n;i++)

         {

             dp[i]=dp[i-];

             if(last[a[i]]==i)

             {

                 int l=fir[a[i]];

                 bool flag=true;

                 for(int k=l+;k<last[a[i]];k++)

                 {

                     if(last[a[k]]>i)

                     {

                         flag=false;

                         break;

                      }

                     l=min(l,fir[a[k]]);

                 }

                 if(flag)

                 {

                     dp[i]=max(dp[i],dp[l-]+sum(l,i));

                 }

             }

         }

         cout<<dp[n]<<endl;

     }

     return ;

 }

巴特西

【dp】codeforces C. Vladik and Memorable Trip

最新文章

热门文章