SRM574 Div1Medium PolygonTraversal

3662 단어 TC dp

[분석] 제목의 범위를 보았을 때 나는 이것이 틀림없이 상압 dp라고 생각했다. 이것은 틀림없이 dp[i][j]를 정의한 것이고 이때 i에서 얻은 점의 집합은 j라고 했다.그러면 문제가 왔습니다. 이런 점들이 있습니다. 제가 i에서 j의 보집 점까지 어떻게 판단할 수 있을까요?이어서 나는 종이 위에 그림을 그렸다.마지막으로 나는 x가 y를 원한다면 원 위의 x가 시계 반대 방향으로 y를 가리키거나 x가 시계 반대 방향으로 y를 가리키면 반드시 약간은 있어야 한다는 것을 발견했다.(왜인지는 내가 어떻게 알고 실천하면 진지해진다).그러면 문제가 해결됩니다!
【코드】

#include 
using namespace std;
#define M 18
#define ll long long
ll dp[M][1<bool mk[M];
int a[M];
int hav;
int n,m;
bool chk(int now,int to,int si){
    int cur;
    bool l=0,r=0;
    cur=(to+1)%n;//         ，  now to         ，to       now，      ，          。
    while(cur!=now){
        if(mk[cur]||si&(1<1;
            break;
        }
        else cur=(cur+1)%n;
    }
    cur=(now+1)%n;
    while(cur!=to){
        if(mk[cur]||si&(1<1;
            break;
        }
        else cur=(cur+1)%n;
    }
    return l&&r;
}
ll DP(int p,int si,int cnt){
    ll &res=dp[p][si];
    if(res)return res;
    if(cnt==n)return res=chk(p,a[1],si);
    res=0;
    for(int i=0;iif(i==p||mk[i]||(si&(1<continue;
        if(chk(p,i,si))res+=DP(i,si|(1<1);
    }
    return res;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
        a[i]--;
        mk[a[i]]=1;
        hav+=(1<cout<return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

SRM574 Div1Medium PolygonTraversal

[분석] 제목의 범위를 보았을 때 나는 이것이 틀림없이 상압 dp라고 생각했다. 이것은 틀림없이 dp[i][j]를 정의한 것이고 이때 i에서 얻은 점의 집합은 j라고 했다.그러면 문제가 왔습니다. 이런 점들이 있습니...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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