简答题
偏难
#22126
T3、染色(color)
T3、染色(color)



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1
#include<cstdio>
#include<algorithm>
#include<cstring>
#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",&t);
while (t--){
ll n;
scanf("%lld",&n);
memset(dp,0,sizeof(dp));
memset(lst,0,sizeof(lst));
anstmp=0;
for (ll i=1;i<=n;i++){
scanf("%lld",&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<=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<bits/stdc++.h>
using namespace std;
#define int long long
int rd() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
void wt(int x) {
static int sta[35];
int f = 1;
if(x < 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<=n;i++) a[i] = rd();
for(int i = 2;i<=n;i++) s[i] = s[i - 1] + (a[i] == a[i - 1]) * a[i];
for(int i = 1;i<=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>
这道题暂未补解析。