简答题 偏难
#22126

T3、染色(color)

T3、染色(color)


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include&lt;cstring&gt; #define ll long long using namespace std;   ll t,anstmp; ll dp[2000005][2]; ll lst[2000005];   struct num{     ll n,last; }a[2000005];   int main(){     ll t;     scanf("%lld",&amp;t);     while (t--){         ll n;         scanf("%lld",&amp;n);         memset(dp,0,sizeof(dp));         memset(lst,0,sizeof(lst));         anstmp=0;         for (ll i=1;i&lt;=n;i++){             scanf("%lld",&amp;a[i].n);             if (lst[a[i].n]) a[i].last=lst[a[i].n];             else a[i].last=0;             lst[a[i].n]=i;             if (a[i-1].n==a[i].n) anstmp=anstmp+a[i].n;         }         for (ll i=1;i&lt;=n;i++){             if (a[i].n==a[i-1].n){                 dp[i][0]=max(dp[i-1][0],dp[i-1][1]);                 dp[i][1]=dp[i-1][1];                 continue;             }             else dp[i][0]=max(dp[i-1][0],dp[i-1][1]);             if (a[i].last) dp[i][1]=max(max(dp[a[i].last][0],dp[a[i].last][1]),max(dp[a[i].last+1][0],dp[a[i].last+1][1]))+a[i].n;         }         printf("%lld\n",max(dp[n][0],dp[n][1])+anstmp);     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include&lt;bits/stdc++.h&gt; using namespace std; #define int long long int rd() { int x = 0, w = 1; char ch = 0; while (ch &lt; '0' || ch &gt; '9') { if (ch == '-') w = -1; ch = getchar(); } while (ch &gt;= '0' &amp;&amp; ch &lt;= '9') { x = x * 10 + (ch - '0'); ch = getchar(); } return x * w; } void wt(int x) { static int sta[35]; int f = 1; if(x &lt; 0) f = -1,x *= f; int top = 0; do { sta[top++] = x % 10, x /= 10; } while (x); if(f == -1) putchar('-'); while (top) putchar(sta[--top] + 48); } namespace work{ const int N = 2e5+5,M = 1e6 + 5; int n,a[M],s[M],f[M],t[M]; void solve() { memset(s,0,sizeof(s)); memset(t,0,sizeof(t)); memset(f,0,sizeof(f)); n = rd(); for(int i = 1;i&lt;=n;i++) a[i] = rd(); for(int i = 2;i&lt;=n;i++) s[i] = s[i - 1] + (a[i] == a[i - 1]) * a[i]; for(int i = 1;i&lt;=n;i++) { f[i] = f[i - 1]; if(t[a[i]]) f[i] = max(f[i],f[t[a[i]] + 1] + a[i] + s[i] - s[t[a[i]] + 1]); t[a[i]] = i; } wt(f[n]);putchar('\n'); } } signed main() { int T = rd(); while(T--) work::solve(); return 0; }</pre>
这道题暂未补解析。