UVA - 10401 Injured Queen Problem(dp)
부상당한 황후는 그 열과 그 주위의 9개의 칸만 공격할 수 있었다.
문자열을 지정합니다. 만약 i번째 문자가 '?' 이라면황후는 임의의 위치에 놓을 수 있다는 뜻이다. 그렇지 않으면 황후가 어느 줄에 놓아야 하는지를 지정하고 몇 가지 놓아야 하는지 물었다.
아이디어:
dp[i][j]는 (i, j) 좌표를 최대 몇 가지 방법이 있음을 나타낸다.
두 가지 시나리오로 나누어 논의합니다.
(1) 바둑알이 이미 방치되었으니 바둑알을 방치하는 줄을 직접 고려한다
(2) 바둑알이 놓여 있지 않고 현재 열 위의 모든 줄을 열거한다
dp[i][j]는 dp[k][j-1]에 달려 있고 k는 제목 조건에 달려 있다.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cctype>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 30;
int vis[N];
ll dp[N][N];
char str[N];
void init() {
memset(vis,0,sizeof(vis));
memset(dp,0,sizeof(dp));
}
bool judge(int j,int k) {
if(abs(j - k) <= 1)
return false;
return true;
}
int main() {
while(scanf("%s",str+1) != EOF) {
init();
int n = strlen(str+1);
for(int i = 1; i <= n; i++) {
if(str[i] >= '1' && str[i] <= '9') {
vis[i] = str[i] - '0';
}else if(str[i] >= 'A' && str[i] <= 'F') {
vis[i] = str[i] - 'A' + 10;
}
}
if(vis[1]) {
dp[vis[1]][1] = 1;
}else {
for(int i = 1; i <= n; i++) {
dp[i][1] = 1;
}
}
for(int i = 2; i <= n ; i++) { //
if(vis[i]) {
for(int k = 1; k <= n; k++) { //
if(judge(vis[i],k))
dp[vis[i]][i] += dp[k][i-1];
}
}else {
for(int j = 1; j <= n; j++) { //
for(int k = 1; k <= n; k++) { //
if(judge(j, k)) {
dp[j][i] += dp[k][i-1];
}
}
}
}
}
ll ans = 0;
for(int i = 1; i <= n; i++) //
ans += dp[i][n];
printf("%lld
",ans);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA - 10986 Sending email(Dijkstra 인접 테이블 + 우선 순위 대기열 최적화)제목 대의: s점에서 t점까지의 최소 거리를 구하는 그림을 주세요. 확인: 적나라한 최단길이지만 n이 너무 크면 인접 행렬을 사용할 수 없기 때문에 Dijkstra에 대한 인접표 + 우선 대기열 최적화가 필요합니다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
