はやし屋

競技プログラミングのメモ きたない

AOJ 0570: Zig-Zag Numbers

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0570

下手の横好きを参考にやりました。
こんなの初めてだq
頭いいなあ(感動のあまり死亡)
dp[今の桁][前の桁の数字][前の桁のupdown][前までのmod][今すべての数字を使えるか];
でやった

本番でときたいもんだなあ

#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<cstring>

using namespace std;

#define MOD 10000

vector < int > A , B; 
int M;

void sub1(vector < int >&q){
  for(int i = q.size()-1 ; i >= 0 ; --i){
    if(q[i] == 0){
      q[i] = 9;
    } else {
      q[i]--;
      return ;
    }
  }
  return ;
}

//     idx,prv,^v,mod,free
int dp[505][10][3][505][2];


// updown 増:0 減:1 0:2
int ZigZag(const vector < int > v , int idx , int prv , int updown , int mod , bool free)
{

  if(idx == v.size())return !mod;

  if(~dp[idx][prv][updown][mod][free])
    return dp[idx][prv][updown][mod][free];
  
  int r = (free ? 9 : v[idx]);
  int ret = 0;

  for(int i = 0 ; i <= r ; ++i,ret %= MOD){

    if(updown == 0 && prv <= i)continue;
 
    if(updown == 1 && prv >= i)continue;

    if(updown == 2 && prv && prv == i)continue;

    int u ;
    if(updown == 2){
      if(prv == 0){
	u = 2;
      } else if(prv > i){
	u = 1;
      } else {
	u = 0;
      }
    } else u = !updown;
    ret += ZigZag(v,idx+1,i,u,(mod*10+i)%M,free|(i!=v[idx]));
  }

  return dp[idx][prv][updown][mod][free] = ret % MOD;
}

int main(){
  string a , b ;cin >> a >> b >> M;
  for(int i = 0 ; i < a.size() ; ++i)
    A.push_back(a[i] - '0');
  for(int i = 0 ; i < b.size() ; ++i)
    B.push_back(b[i] - '0');

  sub1(A);

  memset(dp,-1,sizeof(dp));
  int ra = ZigZag(A,0,0,2,0,false);
  memset(dp,-1,sizeof(dp));
  int rb = ZigZag(B,0,0,2,0,false);

  int ret = (rb - ra + 10000)%10000; 

  cout << ret << endl;
  return 0;
}