【メモ】OUPC Beta C - Power Number
2020/3/21
long_ng.icon < 計算量的にO(N * 10)くらいに落ちてもらわないと困るな(コンテスト中)
感想
文字列の部分文字列系は絶対DPだろって思いながら考察していたが、計算量がどうしても落ちなかった。
長さによって価値が一意に決まるあたりまではわかっていたが、これを全てメモする発想はなかった。
ポイント
どの文字列から生成されたに関わらず、文字列に対して価値の最大値をメモしていくと良い。
実装の注意点として、mapはデフォルトが0なので、負の価値が最初に入ってきた時更新されない。
一度出てきたかどうかも考えないといけない。これはmap.count()でできるらしい。もう一個map用意して書いたが・・・
code:c++
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i) #define rep1(i,N) for(int i=1;i<int(N);++i) typedef long long ll;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const ll INFLL = (ll)1e18+1;
ll N, M, B;
string S; // S.size() = N
vector<string> A;
vec<ll> V; // 10^9
vec<ll> dp;
int main() {
// input part
cin >> N >> M >> B >> S;
A.resize(M);V.resize(M);
rep(i,M){
}
//memo part
map<string, ll> mp;
map<string, int> mpcnt;
rep(j,M){
for(int k = 1; k < bit(10);k++){
string tmp = "";
int cnt = 0;
rep(l, sz){
if(bit(l) & k){
cnt++;
}
}
if(mpcnttmp == 0)mptmp = Vj - (sz - cnt) * B; else chmax(mptmp, Vj - (sz - cnt) * B); }
}
// dp part
dp.assign(N+5, -INFLL);
rep(i,N){
string tmp = "";
rep(j, 10){
if(i + j > N)continue;
}
}
}