Atcoder 400 Number Of Amidakuji 사유, DP
1223 단어 DP
두 기둥 사이의 어느 각도[1,2...n]에 한 줄을 연결할 수 있다(비스듬히 할 수 없고 연결된 선마다 공통된 단점이 없다)
시작점(1,1)은 매번 아래로 내려가고, 직선을 만나면 이 직선의 방향으로 올라간다.
1<=n<=100. 1<=m<=8. 기점에서 (n+1,k)까지 갈 수 있는 몇 가지 연속 방안이 있는지 물어보세요.
모든 직선에는 공통된 단점이 없기 때문에 왼쪽이나 오른쪽을 연속할 수 없다는 것을 의미한다.
비헤이비어 계층으로 DP.매번 결정을 내릴 때마다 아래로 내려간다.(이렇게 결정하면 세 가지가 된다. 좌우, 그리고 움직이지 않는다.)
dp[i][j]를 설정하여 몇 가지 선 그리기 방안을 설정하여 (0,0)에서 출발하여 (i,j)에 도달하도록 한다.
dp[i+1][k] = Σ dp[i][j] *num[j][k] .[num[j][k]는 줄마다 몇 가지 선을 긋는 방안이 있는지 j열에서 k열까지 2^m회 폭력 예처리를 하면 된다.
#include
using namespace std;
typedef long long ll;
typedef pair ii;
const int N=2e2+5,mod=1e9+7;
ll n,m,k,dp[N][N],num[N][N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n>>m>>k;
for(int s=0;s>j)&1;
int b2=(s>>(j+1))&1;
if(b1==b2&&b1) ok=false;
}
if(!ok) continue;
for(int j=0;j>j)&1){
num[j][j+1]++,num[j+1][j]++;
j+=2;
}
else{
num[j][j]++;
j++;
}
}
}
dp[0][0]=1;
for(int i=0;i 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
