(DP)POJ1390 Blocks

传送门：(DP)POJ1390 Blocks

DP看不下去了，先附上郭炜老师的代码

#include<iostream>
#include<cstring>
using namespace std;
const int M=210;
struct Segment{int color;int len;
};Segment segments[M];
int score[M][M][M];int ClickBox(int i,int j,int len){if(score[i][j][len]!=-1)return score[i][j][len];int result=(segments[j].len+len)*(segments[j].len+len);if(i==j) return result;result+=ClickBox(i,j-1,0);for(int k=i;k<=j-1;k++){if(segments[k].color!=segments[j].color) continue;int r=ClickBox(k+1,j-1,0);r+=ClickBox(i,k,segments[j].len+len);result=max(result,r);}return score[i][j][len]=result;;
}int main(){int T;cin>>T;for(int t=1;t<=T;t++){int n;memset(score,0xff,sizeof(score));cin>>n;int lastC=0;int segNum=-1;for(int i=0;i<n;i++){int c;cin>>c;if(c!=lastC){segNum++;segments[segNum].len=1;segments[segNum].color=c;lastC=c;}else segments[segNum].len++;}cout<<"Case "<<t<<": "<<ClickBox(0,segNum,0)<<endl;}return 0;
}