[2019 뉴커머스 국경절 캠프 데이1D][dp]

전송문 제목: 길이가 n인 0~9로 구성된 숫자열이 있는데, 그 중에서 m개 구간의 구간 곱셈%9==0, 조건을 충족시키는 숫자열의 개수%(1e9+7)를 구한 결과
문제풀이: 구간 곱셈이 9의 배수이고 구간 내 인자 3의 개수는 적어도 2개이다. 그 중에서 0과 9는 2개의 3, 3과 6은 1개의 3에 해당하고 나머지 숫자는 0개의 3에 해당한다. 그러면 dp[i][j][k]로 전 i개 안에서 i와 가장 가까운 두 개의 3이 j와 k의 위치에 있는 상황을 나타낼 수 있다. 만약에 두 구간의 오른쪽 단점이 같다면 가장 작은 구간이 조건을 충족시키기만 하면 된다. 이전 과정은 i의 위치에 대해k>=L[i-1]만 사용할 때 dp[i-1][j][k]를 사용하여 i와 관련된 dp값을 업데이트한다. 이렇게 하면 전 i-1개의 합법적인 상황을 사용하여 이전할 수 있다. 이럴 때 첫 번째 i개가 만족하는지>=L[i]를 고려할 필요가 없다. 어차피 뒤에 i+1이 사용한 것도 k>=L[i]의 상황이기 때문이다.한정 전이 과정을 통과하는 dp는 매우 흔히 볼 수 있는 것이다

#include

using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e5+5;
#define debug(x) cout<

ll dp[55][55][55];
int l[55];

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)==2){
        memset(dp,0,sizeof(dp));
        memset(l,0,sizeof(l));
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            l[b]=max(l[b],a);
        }
        dp[0][0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                for(int k=0;k<=j;k++){
                    if(k>=l[i-1]){
                        dp[i][j][k]=(dp[i][j][k]+6*dp[i-1][j][k])%mod;
                        dp[i][i][j]=(dp[i][i][j]+2*dp[i-1][j][k])%mod;
                        dp[i][i][i]=(dp[i][i][i]+2*dp[i-1][j][k])%mod;
                    }
                }
            }
        }
        ll ans=0;
        for(int i=0;i<=n;i++){
            for(int j=0;j<=i;j++){
                if(j>=l[n]){
                    ans=(ans+dp[n][i][j])%mod;
                }
            }
        }
        printf("%lld
",ans);
    }
    return 0;
}