[DP] Atcoder AGC013D. Piling Up

3037 단어 DP헤아리다
처음에 빨간색 x 개가 있었다고 가정하면 n -3 x 파란색
하나의 합법적인 수열에는 여러 개의 초기 x값이 있는데, 가장 작은 x값에 대해 조작하는 과정에서 x는 0이 된다
그럼fi,j,0...1은 i회 조작, 현재 x=j, x가 0이 되었는지 여부를 나타낸다
정답은 ∑fm,i,1
이렇게 하면 중복 안 해도 돼요.
#include 
#include 
#include 

using namespace std;

const int P=1e9+7;

int f[3010][3010][2];

inline void add(int &x,int y){ (x+=y)%=P; }

int main(){
    int n,m;
    cin>>n>>m;
    f[0][0][1]=1;
    for(int i=1;i<=n;i++) f[0][i][0]=1;
    for(int i=0;ifor(int j=0;j<=n;j++)
            for(int k=0;k<=1;k++){
                if(j) add(f[i+1][j-1][k|!(j-1)],f[i][j][k]);
                if(n-j) add(f[i+1][j+1][k],f[i][j][k]);
                if(j) add(f[i+1][j][k|(j==1)],f[i][j][k]);
                if(n-j) add(f[i+1][j][k],f[i][j][k]);
            }
    int ans=0;
    for(int i=0;i<=n;i++) add(ans,f[m][i][1]);
    cout<return 0;
}
트리 DP
UVA - 11324 The Largest Clique 강연통 축소점 + 기억화 dp

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage