【xsy1172】染色 dp

题目大意：现有$n$条排成一行的木板，每个木板有一个目标颜色。你每次能将一个区间内的木板分别染成它们的目标颜色，而这次染色的代价为这个区间内不同目标颜色的木板的数量的平方。问将全部木板染成目标颜色的最小代价。

数据范围：$n≤50000$，颜色数量$≤50000$。

这题我们显然可以$dp$，令$f[i]$表示把前i个点覆盖完的最小代价，显然$f[i]=min(f[j-1]+w(j,i)^2)$ 其中$w(j,i)$表示区间$[i,j]$中的颜色数量。

这一题有一个隐藏条件，就是总代价不会超过$n$，这个是显然的。

所以，当区间$[i,j]$中的颜色数量$>\sqrt{n}$时，就显然不是最优的。

考虑到$f[i]$是非降的，那么我们处理一个数组$pre[i][j]$表示：从第$i$号点开始，恰好包含$j$种颜色的区间最左侧的端点编号。

我们从$1$到$\sqrt{n}$枚举$j$，每次$O(n)$的时间从右往左扫，详情见代码。

然后就愉悦地做完了，时间复杂度为$O(n*\sqrt{n})$。

 #include<bits/stdc++.h>

 #define M 100005

 #define INF 1000000005

 using namespace std;

 int n,a[M]={},pre[M][]={},f[M]={},cnt[M]={},sum=;

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++) scanf("%d",a+i);

     for(int j=;j*j<=n;j++){

         for(int i=n,k=n;~i;i--){

             while(k>=&&sum<=j){

                 cnt[a[k]]++;

                 if(cnt[a[k]]==) sum++;

                 k--;

             }

             pre[i][j]=k+;

             cnt[a[i]]--; if(!cnt[a[i]]) sum--;

         }

     }

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

         f[i]=INF;

         for(int j=;j*j<=n;j++)

         f[i]=min(f[i],f[pre[i][j]]+j*j);

     }

     printf("%d\n",f[n]);

 }

巴特西

【xsy1172】染色 dp

最新文章

热门文章

巴特西

【xsy1172】 染色 dp

最新文章

热门文章

【xsy1172】染色 dp