【題解】ZeroJudge c481: pD 彩色紙條

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c481
【解題想法】DP

#include <iostream>
#include <cstring>
using namespace std;

int t, n, m, a[205], dp[205][205];

int main(){
    cin >> t;
    while(t--){
        memset(dp, 0x3F, sizeof(dp));
        cin >> n >> m;
        for (int i = 1; i <= n; i++){
            cin >> a[i];
            dp[i][i] = 1;
        }
        for (int i = n; i > 0; i--){
            for (int j = i+1; j <= n; j++){
                for (int k = i; k+1 <= j; k++){
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]);
                }
                if (a[i] == a[j]) dp[i][j]--;
            }
        }
        cout << dp[1][n] << "\n";
    }
}
分享本文 Share with friends