問題
http://topcoder.bgcoder.com/print.php?id=2810
スペースと改行からなる文字列がある。
最初は改行のみ入力されている。
このとき、与えられた配列が(3,2,2)であるなら
space space space 改行 space space 改行 space space 改行となるようにしたい。
可能な操作は以下の通り。
①spaceの追加
②spaceの削除
③直前のspaceと改行のコピー
(space 改行 space space 改行で2つめの改行の前にカーソルを合わせると
space 改行 space space 改行 space space 改行)
このとき、必要な最小の操作回数を求める。
解き方
例を出して操作をシミュレーションしてみる。
{1,2,3}のとき
{1}→{1,1}→{1,2}→{1,2,2}→{1,2,3}と操作回数は６回。
{1,3,2}のとき
{1}→{1,1}→{1,2}→{1,2,2}→{1,3,2}と操作回数は6回。
ここでp[]={a,c,b} a<=b<=cのとき,
前の数より大きいものについて,(c-a)
それに加えてa+配列数-1で作れそうなことがわかる。
大きな例で確認してみる
{1,4,3,2,3}のとき
{1}→{1,1}→{1,2}→{1,2,2}→{1,2,3}→{1,2,2,3}→{1,3,2,3}→{1,3,3,2,3}
→{1,4,3,2,3} 操作回数は9回。
1(最初の要素) + 5(配列数) -1 +(4-1)+(3-2) =1+4+3+1=9
ということで複雑な例でも満たすことがわかる。
コード
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()
class WhiteSpaceEditing {
public: int getMinimum(vector<int> lines) {
int ret=lines.size()-1+lines[0];
FORE(i,1,lines.size()){
if(lines[i]>lines[i-1]){
ret+=abs(lines[i]-lines[i-1]);
}
}
return 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()
class WhiteSpaceEditing {
public: int getMinimum(vector<int> lines) {
int ret=lines.size()-1+lines[0];
FORE(i,1,lines.size()){
if(lines[i]>lines[i-1]){
ret+=abs(lines[i]-lines[i-1]);
}
}
return ret;
}
};