100개의 동적 계획 – 34 UVA 10559 Blocks 상태의 정의 상태 전환 방정식

그래, 내가 생각한 것은 매거 결정...
구간DP 같은 느낌이라니.응.그렇긴 한데, 단지 DP에 추가 조건을 붙여야 할 뿐이다
정의 상태 dp[i][j][k]는 구간 i~j를 표시하고 오른쪽에 j와 같은 색의 네모난 블록의 최대 값을 추가합니다
매번 가장 오른쪽을 없애는 것을 고려한다. 가장 오른쪽을 없애는 것을 고려한다면 두 가지 없애는 방법이 있다. 첫 번째는 바로 이번에 없애는 것이고, 두 번째는 남겨두고 나중에 없애는 것이다.
두 번째 없애는 방법은 i~j에서 j를 제외한 각 단락과 j가 같은 색의 블록의 오른쪽을 매거하는 것이다. 현재의 가장 오른쪽의 블록을 이 단락의 가장 오른쪽에 붙이는 것을 고려하면 언어 감각이 좀 명확하지 않다.
상태 이동 방정식은 dp[i][j][k]=dp[i][ri][0]+(j-ri+k)*(j-ri+k)이다. 그 중에서ri는 오른쪽 끝을 제거한 후의 새로운 시작점, 즉 오른쪽 첫 번째 j와 같은 색 블록이 없는 위치이다.
두 번째 이동은 각 단락이 j와 같은 색의 오른쪽을 매거하는 것이다. l로 가정하면 방정식은 dp[i][j]=max(dp[i][j][k], dfs(dp[i][le][k+j-ri])+dfs(dp[le+1][ri][0]))가 두 단락의 합에 해당한다.
좋은 제목이네요.

#include 
#include 
#include 

using namespace std;
const int maxm=210;

int times,n,kcase,color[maxm],dp[maxm][maxm][maxm],dfs(int i=1,int j=n,int k=0);
void init();

int main(){
    ios_base::sync_with_stdio(false);
    cin>>times;
    while(times--){
        cin>>n;
        init();
        for(int i=1;i<=n;++i)
            cin>>color[i];
        cout<j)
        return 0;
    if(dp[i][j][k])
        return dp[i][j][k];
    int ri=j;
    while(ri>=i&&color[j]==color[ri])--ri;
    dp[i][j][k]=dfs(i,ri,0)+(j-ri+k)*(j-ri+k);
    for(int le=i;le<=ri;++le)
    if(color[le+1]!=color[le]&&color[le]==color[j])
    dp[i][j][k]=max(dfs(i,le,j-ri+k)+dfs(le+1,ri,0),dp[i][j][k]);
    return dp[i][j][k];
}