codeforces 107C Arrangement(상압 dp)

제목:
n명과 n개의 좌석을 주고 m대 제한을 주며 매 쌍의 제한은ai라는 사람의 좌석을bi라는 사람의 앞에 배열해야 한다.현재 조건을 충족시키는 y-2001대 사전순의 좌석 배열을 요구한다.
문제풀이: 문제가 아주 좋고 처리 방법이 매우 특별하다.이런 문제에 대해 우리는 먼저 폭력을 생각해 본다. 그것은 바로 1부터 시작하는 각종 조건을 만족시키는 서열을 매거하는 것이다. 사실 매거할 때 우리는 이렇게 최적화할 수 있다. 먼저 첫 번째로 줄을 서는 사람을 매거한 다음에 줄을 서 있는 사람을 기준으로 대응하는 배열수를 계속 계산한다. 만약에 배열수가 원하는 y보다 많으면 이 줄의 사람은 합법적이다. 작으면 y에서 뺀 배열수를 계산한다.2위는 아까의 조작을 반복한다.
배열수의 계산은 dp로 할 수 있으며, 상압 dp는 O(2^n)에서 계산할 수 있으며, 시간은 충분히 충분하다.
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define B(x) (1<=n) { f=0; puts("The times have changed"); break; }
                memset(dp,0,sizeof dp);
                dp[0]=1;
                for(int s=0;s<=full;s++)
                if(dp[s])
                {
                    int cnt=__builtin_popcount(s);
                    for(int k=0;k=dp[full])
                    y-=dp[full];
                else
                {
                    mark[ans[i]]=1;
                    break;
                }
            }
        }
        if(!f)continue;
        for(int i=0;i

좋은 웹페이지 즐겨찾기