P7414 [USACO21FEB] Modern Art 3 G
题目大意
给你一个长度为 n n n的数组，要求你在一个全部为 0 0 0的数组中每次将一个区间 [ i , j ] [i,j] [i,j]赋为同一个值，当前的赋值可以覆盖之前的值，求最少要赋值多少次才能使这个数组与给定数组相同。
1 ≤ n ≤ 300 1\leq n\leq 300 1≤n≤300
题解
可以使用区间DP。
设 f i , j f_{i,j} fi,j为赋值完区间 [ i , j ] [i,j] [i,j]，使得这一段区间与给定数组相同的最少赋值次数，则转移式为
f i , j = f i , k + f k + 1 , j − ( a i = = a j ) f_{i,j}=f_{i,k}+f_{k+1,j}-(a_i==a_j) fi,j=fi,k+fk+1,j−(ai==aj)
其中 i ≤ k < j i\leq k<j i≤k<j
如果一段区间 [ i , j ] [i,j] [i,j]的两端相同，显然可以先赋值 [ i , j ] [i,j] [i,j]再去赋值 [ i + 1 , j − 1 ] [i+1,j-1] [i+1,j−1]。如果区间 [ i + 1 , j − 1 ] [i+1,j-1] [i+1,j−1]中有一个点 k k k与 i i i在给定数组上的值相同且在赋值完 [ i , j ] [i,j] [i,j]后不需处理，会在 f i , k f_{i,k} fi,k中被统计；如果 k k k与 j j j的在给定数组上的值相同，会在 f k , j f_{k,j} fk,j中被统计。这样做可以保证所有可能都会被统计。
初始值 f i , i = 1 f_{i,i}=1 fi,i=1， f i , j = + ∞ ( i < j ) f_{i,j}=+\infty(i<j) fi,j=+∞(i<j)，答案为 f 1 , n f_{1,n} f1,n。文章来源：https://www.toymoban.com/news/detail-697952.html
时间复杂度为 O ( n 3 ) O(n^3) O(n3)。文章来源地址https://www.toymoban.com/news/detail-697952.html
code
#include<bits/stdc++.h>
using namespace std;
int n,a[305],f[305][305];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
f[i][i]=1;
}
for(int l=2;l<=n;l++){
for(int i=1,j=l;j<=n;i++,j++){
f[i][j]=1e9;
for(int k=i;k<j;k++){
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]-(a[i]==a[j]));
}
}
}
printf("%d",f[1][n]);
return 0;
}
到了这里，关于USACO21FEB Modern Art 3 G的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
