JOISC2009 chopsticks. 塗り箸 (Chopsticks)
Difficulty:None
問題文
#JOISC2 #JOI
#区間DP
問題
解法
解説の$ k\leq r-1は$ k < r-1の間違いだと思われる
実装
累積和を取って色々やろうとした跡が残っている
提出コード
code:cpp
int n;
int dp301301;
int a301;
int b52301;
int f(int l,int r){
deb(l,r);
if(dplr!=n)return dplr;
if(r-l==1)return dplr=1;
if(l>=r)return dplr=0;
rep(k,l,r-1){
chmin(dplr,f(l,k+1)+f(k+1,r)-(al==ar-1));
}
return dplr;
}
bool solve(){
cin >> n;
Fill(dp,n);
STR(s);
rep(i,n){
if(islower(si))ai=si-'a';
else ai = si-'A'+26;
b[ai]i+1++;
}
rep(i,52){
rep(j,1,n+1){
bij += bij-1;
}
}
O(f(0,n));
return false;
}