Pの競プロ記

競技プログラミングに関することを書きます。

AOJ 2182 Eleven Lover

概要


問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2182

80000桁以下の数字(文字列)が与えられます。
その中で11の倍数である部分文字列の個数を求める問題です。


解法


動的計画法(DP)で求めることができます。

int dp[(左から見て)何桁目か][11でMODをとった値] = 場合の数
のような配列を作ってやればよいです。

一番左の桁に0がついてはいけないので、0以外の時にdp[現在の桁][その桁の数]++してやります。


ソースコード

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int dp[80001][11];

int main(){
  string s;

  while(cin >> s){
    if(s == "0") break;
    
    int sz = s.size();
    memset(dp, 0, sizeof(dp));
    
    for(int i = 0; i < sz; i++){
      int val = s[i] - '0';
      
      for(int j = 0; j < 11 && i != 0; j++){
        dp[i][(j * 10 + val) % 11] += dp[i - 1][j];
      }

      if(val != 0) dp[i][val]++;
    }

    int ans = 0;
    for(int i = 0; i < sz; i++) ans += dp[i][0];
    
    cout << ans << endl;
  }
  return 0;
}