牛客周赛137补题

D 小苯的序列涂色

观察数据范围，发现才5000，那么可以考虑 n²的方法，n²的算法不多，dp算一种，观察问题，问的是最小总代价（凡是说最小代价，最大方案，之类的一般都可以考虑dp），故而考虑dp，用dp[i] 表示从1到i位置所消耗的最小代价。

选定i了，那么i之后的我们先不考虑，所以一定有个染色操作是以i为结尾的，我们遍历1-i去找最小的异或值才可以，找到左边界之后，我们还要处理1-左边界这些数，如果直接+dp[j-1]肯定不对，因为这个题是可以重复染色的，所以应该去j-1到i-1中找最小值才行，可是这样又要加一层循环，不如从i开始倒序循环，j的范围是从i到1，同时维护最小的dp值，最终可以得到结果。

因为对于每一个i来说，dp[i]都是1-i染色的最小代价，所以最后得到的dp[n]也是最小的。

code

void solve()
{cin>>n;vi a(n+1),b(n+1);for(int i=1;i<=n;i++){cin>>a[i];b[i]=b[i-1]^a[i];}vi dp(n+1,1e18);dp[0]=0;for(int i=1;i<=n;i++){dp[i]=dp[i-1]+a[i];int mi=1e18;for(int j=i;j>=1;j--){mi=min(mi,dp[j-1]);dp[i]=min(dp[i],mi+(b[i]^b[j-1]));}}cout<<dp[n]<<endl;
}