本文共 1153 字，大约阅读时间需要 3 分钟。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 10 #define Faster ios::sync_with_stdio(false),cin.tie(0)11 #define Read freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)12 #define Close fclose(stdin),fclose(stdout)13 const int maxn = 150;14 using namespace std;15 const int MOD = 1e9+7;16 typedef long long ll;17 18 int a[maxn];19 int dp[maxn][maxn];20 //dp[i][j],从区间i -> j 穿的最少的衣服数量21 22 int main(){23 Faster;24 int t;25 cin >> t;26 int cnt = 0;27 while(t--){28 cnt++;29 int n;30 cin >> n;31 for(int i = 1;i <= n;i++){32 cin >> a[i];33 }34 //初始化，每件都穿上35 for(int i = 1;i <= n;i++){36 for(int j = i;j <= n;j++){37 dp[i][j] = j-i+1;38 }39 }40 for(int i = n-1;i >= 1;i--){41 for(int j = i+1;j <= n;j++){42 dp[i][j] = dp[i+1][j] + 1;43 for(int k = i;k <= j;k++){44 if(a[i] == a[k]){45 dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]);46 }47 }48 }49 }50 cout << "Case " << cnt << ": " << dp[1][n] << endl;51 } 52 return 0;53 }
转载于:https://www.cnblogs.com/ouyang_wsgwz/p/9200869.html