問題
http://community.topcoder.com/stat?c=problem_statement&pm=12198&rd=15178
ある数字の列が与えられる。
数字列の左側から順に、空白から始めてその左側もしくは右側に足していって新たな数字の列を作ることができる。
また、最低限満たしたい数字の列も与えられる。
このとき、最低限満たしたい数字の列よりも大きく、かつできるだけ小さい数字列を求める。
ただしそのような数字の列が存在しない場合は””を返す。
解き方
順に考えると手掛かりがないので、逆の操作をすることを考える。
逆の操作を考えると、最後の文字列はそれまでできた文字列の左側もしくは右側に足すことになる。
また、最後から２番目の文字列はそれまでにできた文字列の左側、もしくは右側に、、、とｄｐに落とすことができる。
ｄｐの状態としては、これまで左側に振り分けた文字、右側に振り分けた文字と、それぞれ振り分けた数字と最低限満たしたい文字列との大小関係を保存する。
大小関係は文字列数分振り分けた後に、最小文字以上かどうかを判定するのに利用する。
各ｄｐでの判定については、左側に振り分けた文字については左から順に決まっていくので、それまで＝であったときのみ大小関係を新たに判定する。
右側に振り分けた文字は右側から決まっていくので、毎回大小関係を判定する。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int n;
string digits,lowerbound;
string dp[60][60][3][3];
int used[60][60][3][3];
class LeftRightDigitsGame2 {
public:
string rec(int l,int r,int cmpl,int cmpr){
if(used[l][r][cmpl][cmpr])return dp[l][r][cmpl][cmpr];
if(n-l-r-1<0)return (cmpl==2 || (cmpl==1&&cmpr>=1)) ? "" : "#";
int cmpl2=cmpl,cmpr2=cmpr;
dp[l][r][cmpl][cmpr]="#";
used[l][r][cmpl][cmpr]=1;
string str="#";
if(cmpl==1){
if(digits[n-l-r-1]>lowerbound[l])cmpl2=2;
if(digits[n-l-r-1]<lowerbound[l])cmpl2=0;
}
str=rec(l+1,r,cmpl2,cmpr);
if(str!="#")dp[l][r][cmpl][cmpr]=digits[n-l-r-1]+str;
if(digits[n-l-r-1]>lowerbound[n-r-1])cmpr2=2;
if(digits[n-l-r-1]<lowerbound[n-r-1])cmpr2=0;
str=rec(l,r+1,cmpl,cmpr2);
if(str!="#"){
if(dp[l][r][cmpl][cmpr]=="#")dp[l][r][cmpl][cmpr]=str+digits[n-l-r-1];
else dp[l][r][cmpl][cmpr]=min(dp[l][r][cmpl][cmpr],str+digits[n-l-r-1]);
}
return dp[l][r][cmpl][cmpr];
}
string minNumber(string digits_, string lowerBound_) {
digits=digits_;
lowerbound=lowerBound_;
n=digits.size();
memset(used,0,sizeof(used));
string ret=rec(0,0,1,1);
return ret=="#" ? "" : ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int n;
string digits,lowerbound;
string dp[60][60][3][3];
int used[60][60][3][3];
class LeftRightDigitsGame2 {
public:
string rec(int l,int r,int cmpl,int cmpr){
if(used[l][r][cmpl][cmpr])return dp[l][r][cmpl][cmpr];
if(n-l-r-1<0)return (cmpl==2 || (cmpl==1&&cmpr>=1)) ? "" : "#";
int cmpl2=cmpl,cmpr2=cmpr;
dp[l][r][cmpl][cmpr]="#";
used[l][r][cmpl][cmpr]=1;
string str="#";
if(cmpl==1){
if(digits[n-l-r-1]>lowerbound[l])cmpl2=2;
if(digits[n-l-r-1]<lowerbound[l])cmpl2=0;
}
str=rec(l+1,r,cmpl2,cmpr);
if(str!="#")dp[l][r][cmpl][cmpr]=digits[n-l-r-1]+str;
if(digits[n-l-r-1]>lowerbound[n-r-1])cmpr2=2;
if(digits[n-l-r-1]<lowerbound[n-r-1])cmpr2=0;
str=rec(l,r+1,cmpl,cmpr2);
if(str!="#"){
if(dp[l][r][cmpl][cmpr]=="#")dp[l][r][cmpl][cmpr]=str+digits[n-l-r-1];
else dp[l][r][cmpl][cmpr]=min(dp[l][r][cmpl][cmpr],str+digits[n-l-r-1]);
}
return dp[l][r][cmpl][cmpr];
}
string minNumber(string digits_, string lowerBound_) {
digits=digits_;
lowerbound=lowerBound_;
n=digits.size();
memset(used,0,sizeof(used));
string ret=rec(0,0,1,1);
return ret=="#" ? "" : ret;
}
};