LightOJ(1422)——Halloween Costumes

まず、私はやはり自分を褒めて、独立して考え始めました.最後の考えは間違っていますが、少なくとも近づいています.だから、もっと頑張りましょう.
タイトル:
今その人はパーティーに参加して、それから全部でn日で、毎日着る服の番号はそれぞれc[i]です.
この人は一度に1枚の服を着たり、一度に任意の複数の服を脱いだりすることができます.もちろん服の外で服を着ることもできます.
そして、もしこの服が脱がれたら、今度はもう着られません.もし私たちがこの服が必要なら、私たちはもう一度別の服を買うしかありません.
最後に、もしすべてのパーティーに参加するなら、彼が必要とする最低の服の数はいくらですか.
たとえば、最初の例です.
4
1 2 1 2私たちはまず1を着て、それから2を着て、それから1を脱いで、それからこの時2の服がありません.だから、私たちはまだ2の服が必要です.だから、最後に全部で3つの服が必要です.
考え方:
この問題の主な難点は、まだ存在する服をいつ利用できるかを判断することです.
dp[i][j]をi~j区間で必要とされる最低限の衣類の数として定義する.
次の考え方が巧みだと思います.
なぜ後ろから前に向かって押すのか、まるで01リュックがなぜ後ろから前に向かって押すのかのように、前の影響を防ぐように後ろに向かっているような気がします(でもここは正直私自身もよくわかりませんが)ので、こちらでは逆forをしています.
1)dp[i][i]=1,これは初期化dpである
2)s番目の服を単独で持ち出すと、dp[s][e]=dp[s+1][e]+1になります.後に1をつけるのは、ここでもう1つ選ぶからです.
3)次に中間点kを列挙し、c[s]=c[k]のとき、ここではk日目までi日目の服を着ていることを意味し、dp[s][e]=min(dp[s][e],dp[s+1][k-1]+dp[k][e]);後ろの式は私たちがsという服を選ばないからです.なぜk-1番目に列挙したのかというと、もし後ろのk~e区間にc[k]==c[?]が存在したら、では、私たちのdp[k][e]はこの中で最適な結果を取るため、最初の区間はk-1までです.
いくつかのわかりやすいブログをお勧めします.http://www.cnblogs.com/neopenx/p/4050003.html        http://www.cnblogs.com/kuangbin/archive/2013/04/29/3051392.html
http://www.cnblogs.com/ziyi--caolu/archive/2013/08/04/3236035.html

#include
#include
#include
#include
using namespace std;
#define maxn 111
#define inf 99999999
int c[maxn];
int dp[maxn][maxn];
int main(){
	int T,j=1;
	scanf("%d",&T);
	while(T--){
		memset(dp,0,sizeof(dp));
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&c[i]);
			dp[i][i]=1;
		}
		for(int s=n-1;s>=1;s--){
			for(int e=s+1;e<=n;e++){
				dp[s][e]=dp[s+1][e]+1;
				for(int k=s;k<=e;k++){
					if(c[s]==c[k]) dp[s][e]=min(dp[s][e],dp[s+1][k-1]+dp[k][e]);
				}
			}
		}
		printf("Case %d: %d
",j++,dp[1][n]);
	}
}