DP
상용상압방법:이진법
대부분의 상압 문제에 대해 통상적으로 1과 0 두 가지 상태만 있기 때문에 f수조를 다음과 같이 표시할 수 있다.
f[k1][k2][k3]…[kn]
그 중
kn은 1 또는 0
만약 이렇게 한다면 시간의 복잡도와 공간의 복잡도에서 상압 후의 DP와 크게 다르지 않은데 코드의 복잡도에 관해서는... 그래서 이런 상태를 "표시하기는 어렵지만 표시하기는 쉽다"라고 말한 것이다
그래서 우리는 상압을 도입했다. 상압 후에 하나의 수조만 있으면 이전 방식에 따라 여러 개의 수조가 저장한 상태 정보를 저장할 수 있고 구체적인 실현은 다음과 같다.
f[(k1<<1)+(k2<<2)+(k3<<3)+…+(kn<
f[1][0][1][1]가 먼저
f[1011], 최종
f[11]
(20+21+23=11)
상압의 이점
특히 이진법 구조의 상압에 대해 어떤 원소의 존재 여부를 판단하는 데는 & 한 번만 있으면 대응 위치를 찾을 수 있고 상태 이동 과정에서 저장 수조에 대한 가감에서도 |,^로 원래의 +,-를 대체하여 더욱 빠른 운행 속도를 얻을 수 있다.
상압의 문제형 특징도 매우 뚜렷하다. 수조의 크기가 제한되어 상압류의 문제 데이터가 매우 작다. 보통 2진법 상압 중 n의 크기가 18을 넘지 않기 때문에 데이터 범위를 세밀하게 관찰함으로써 문제가 상압 문제일 수 있는지 추측할 수 있고 문제의 뜻을 통해 스스로 분석하여 규칙을 찾아낼 수 있다.
상압 DP 쓰기 방법이 비교적 많기 때문에 서로 다른 압축 방식과 대응 전이 방정식은 서로 다른 시간 복잡도와 공간 복잡도를 얻을 수 있다. 이것은 A문제의 관건이 되는지의 관건이 되고 연습을 많이 하고 느낌을 찾으며 진지하게 생각해야 한다.
몇몇 예제
T1 단어 게임(soj125)
제목 설명
아이오와 아오는 단어 게임을 하고 있다.
그들은 모음 자모만 포함된 단어를 번갈아 말하고, 다음 단어의 첫 번째 자모는 반드시 앞 단어의 마지막 자모와 일치해야 한다.게임은 어떤 단어든 시작할 수 있다.어떤 단어든 두 번 말하면 안 되고, 게임에서는 주어진 사전에 포함된 단어만 사용할 수 있다.게임의 복잡도는 게임에서 사용하는 단어의 길이 총화로 정의된다.
프로그램을 작성하여 주어진 사전을 사용하여 이 게임이 달성할 수 있는 게임의 최대 복잡도를 구하십시오.
입력 형식
파일의 첫 줄을 입력하면 자연수 N(1≤N≤16)을 나타내고, N은 한 사전의 단어 수를 나타내며, 아래의 줄마다 사전의 한 단어를 포함하며, 단어마다 알파벳 A, E, I, O 및 U로 구성된 문자열로 각 단어의 길이는 100보다 작고 모든 단어는 다르다.
출력 형식
출력 파일은 게임의 최대 복잡도를 나타내는 줄만 있습니다.
샘플 데이터 1
5 IOO IUO AI OIOI AOOI 입력
출력 16
비고[샘플 설명] AOOI IUO OIOI IOO length=16
해결:
너무 직설적인 느낌의 DP+01 백팩도 클래식한 입문문제예요. 더 이상 말 안 해도 돼요. 생각 안 해도 돼요. 그냥 붙여주세요.
#includescanf("%s",s);
len[i]=strlen(s);
h[i]=s[0]-'A';t[i]=s[len[i]-1]-'A';
f[1<1<1<for(int i=1;i1<<16);i++){
if(!f[i]) continue;
for(int j=0;jif((1<continue;
if(h[j]!=ed[i])continue;
if(len[j]+f[i]>f[i|(1<1<1<1<cout< T2 목장의 배치(poj3254)
제목 설명
Farmer John은 직사각형의 목장을 새로 샀는데 이 목장은 N행 M열(1<=M<=12;1<=N<=12)로 나누어져 각 칸마다 정사각형의 땅이다.
FJ는 목장의 어느 땅에 맛있는 풀을 심어 젖소들이 먹을 수 있도록 할 계획이다.유감스럽게도 일부 토지는 상당히 척박해서 방목용으로 쓸 수 없다.그리고 젖소들은 잔디밭을 독점하는 느낌을 좋아하기 때문에 FJ는 두 개의 인접한 땅을 선택하지 않는다. 즉, 두 개의 잔디밭이 공공변을 가진 곳이 없다는 것이다.물론 FJ는 아직 어떤 땅에 풀을 심을지 결정하지 못했다.
호기심 많은 농장주로서 FJ는 잔디의 총 덩어리 수를 고려하지 않으면 모두 몇 가지 재배 방안이 그가 선택할 수 있는지 알고 싶어 한다.물론 새로운 목장을 황폐화하고 그 어떤 땅에도 풀을 심지 않는 것도 하나의 방안이다.당신이 FJ를 도와 이 총 방안의 수를 계산해 주세요.
입력 형식
첫 번째 줄: 두 개의 정수 N과 M을 빈칸으로 구분하여 두 번째...N+1줄: 줄마다 공백으로 구분된 M개의 정수를 포함하고 각 토지의 상태를 설명합니다.입력한 i+1줄은 i행의 땅을 설명합니다.모든 정수가 0이나 1이면 이 땅이 충분히 비옥하다는 뜻이고, 0이면 이 땅이 풀을 심기에 적합하지 않다는 뜻이다.
출력 형식
목장 분배 총 방안의 수를 100000000의 나머지로 나누는 정수를 출력합니다.
샘플 데이터 1
2 3 1 1 1 0 1 0 을 입력합니다.
출력
비고[예시 설명] 토지 상황은 다음과 같다. 1 1 1 0 10 다음 그림에 따라 비옥한 각 토지의 번호: 1 2 3 0 4 0
잔디 한 조각만 개척하면 4가지 방안이 있다. 하나, 둘, 셋, 넷 중 하나를 선택한다.두 개의 잔디를 개척하면 세 가지 방안이 있다. 13, 14, 34.잔디 세 개를 고르는 방안은 하나뿐이다. 하나, 둘, 셋, 넷.목장을 황폐화시키는 방안은 총 4+3+1+1=9종이다.
[데이터 범위]
50%의 데이터에 대해 1≤N≤5를 만족시킨다.1≤M≤6은 100% 데이터에 대해 1≤N≤12를 만족시킨다.1≤M≤12.
해석
또한 하나의 고전적인 주제이다. f[i][k]를 켜면 현재 i열에 위치하고 있음을 나타낸다. 각 줄의 k종 방목 방식의 상황 총수에 대해 먼저 전 줄을 판단하고 현재 줄의 지형이 가능한지 판단한 다음에 상황을 누적해야 한다.
#include// cout<
}
predo(-1,0);
for(int i=1;i<=tot;i++){
if(fit(ld[1],plan[i])){
f[1][i]=1;
}
}
for(int i=2;i<=n;i++){
for(int j=1;j<=tot;j++){
for(int k=1;k<=tot;k++){
if(f[i-1][j]){
if(fit(ld[i],plan[k])){
if(fit(plan[j],plan[k])){
f[i][k]=(f[i][k]+f[i-1][j])%mod;
}
}
}
}
}
}
// for(int i=1;i<=tot;i++)cout<
for(int i=1;i<=tot;i++){
ans=(ans+f[n][i])%mod;
}
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
leetcode 퀴즈 투어(1)이것은 문제 풀이 여행의 첫 번째 편으로 귀속에 대한 총결로 제목은 주로 체인 테이블과 두 갈래 나무를 포함한다.이전에 귀환을 고려할 때 귀환의 한 걸음 한 걸음 조작을 고려했기 때문에 세부 사항을 모두 똑똑히 알아...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
