Codeforces gym 102219 F. Military Class(상압 dp)

11369 단어 dp
링크: F. Military Class
제목: 1-n의 서열 두 개를 주고 서열 중의 두 개의 짝을 지어야 한다. 짝짓기의 두 개의 절대 값의 차이는 e보다 작고 k의 제한도 있다. 즉, u는 v와 짝짓기를 할 수 없다.
사고방식: e의 값이 4밖에 없는 것을 관찰했다. 즉, 현재 수가 가장 많고 9개의 수와 짝을 짓는 것을 볼 수 있기 때문에 상압은 현재 위치까지 짝을 짓는 것을 나타낼 수 있다. 이미 9개의 위치 중 몇 개를 사용했는데 충돌 여부를 판단할 때 이전 상태를 오른쪽으로 한 자리 옮겨 현재 위치와 대응해야 한다.
코드:
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll ;
const int maxn=2e3+7;
const int mod = 1e9 +7;
ll dp[maxn][maxn],mp[maxn][maxn],ans;
int n,e,k;
int main(){
    cin>>n>>e>>k;
    for(int i = 0,u,v; i < k; i ++){
        scanf("%d%d",&u,&v);
        mp[u][v] = 1;
    }
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int pre = 0; pre < (1 << 2 * e + 1); pre ++){
            for(int j = - e; j <= e; j ++){
                int k = i + j;
                if(k < 1 || k > n || mp[i][k]) continue;
                if((pre >> 1) & (1 << (j + e)))continue;
                dp[i][(pre >> 1)|(1 << (j + e))] = (dp[i][(pre >> 1)|(1 << (j + e))] + dp[i-1][pre]) % mod;
            }
        }
    }
    for(int i = 0; i < (1 << 2 * e + 1); i++){
        ans = (ans + dp[n][i]) % mod;
    }
    printf ("%lld
",ans);



}
@blocz/react-responsive v3가 종료되었습니다.
JAVA- 소스 코드 분할(Package 사용)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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