AUPC 2018 day3 A: Internet Protocol Address
制約
与えられる文字列は4文字以上12文字以下
方針
DPか全探索。どちらでも手間はかわらず。
ソースコード
int dp[20][20]; int main() { string s; cin >> s; dp[0][0] = 1; rep(i, s.size()) rep(j, 4){ int num = 0; for(int k = i; k < i + 3 && k < s.size(); k++){ num *= 10; num += s[k] - '0'; if(num < 256){ dp[k + 1][j + 1] += dp[i][j]; } if(k == i && num == 0) break; } } cout << dp[s.size()][4] << endl; return 0; }