Codeforces 111C Petya and Spiders 문제 해결 & 코드
4067 단어 dpcodeforces
사고방식: dp라dp라=dp방정식은 어떤 전이 조건이 존재할 때dp[i][sta][stb]=max(dp[i-1][stc][sta]+s[sta], dp[i][sta]][stb]) 중 i는 행수[사실 가장 큰 [2진법으로 열거할 수 없는 제곱으로 복잡하게 보낸 그 sta는 현재 행(제i행)의 상태를 나타내고, stb는 다음 행(제i+1행)의 상태를 나타내며, stc는 dp방정식에서 이전 행(i-1행)의 상태를 나타낸다.=1, 그러면 check를 옮기는 방식은 현재 줄을 검사하는 것이다. Sta와 그의 이웃을 진행하거나 연산을 하고 stb와 stc와 동시에 진행하거나 연산을 한다. 그리고 만약에 이렇게 해서 모두 1의 Stack을 얻게 된다면 이 상태는 존재할 수 있다는 것을 의미한다. 결과에 대해== 맨 뒷줄의 다음 줄이 모두 0이고 마지막 줄이 성공적으로 옮기면 모두 유효한 상태이다. 가장 작은 것을 찾아내면 된다.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxa=1<<6;
int n,m,maxm,ans,s[maxa],dp[45][maxa][maxa];
bool check(int sta1,int sta2,int sta3)
{
return ((sta1 | (sta1<<1) | (sta1>>1) | sta2 | sta3) & (maxm-1))==(maxm-1);
}
int cal(int x)
{
int r=0;
while(x)
{
if(x&1)r++;
x>>=1;
}
return m-r;
}
int main(void)
{
scanf("%d%d",&n,&m);
if(m>n)swap(m,n);
maxm=(1<<m);
memset(dp,-1,sizeof(dp));
for(int i=0;i<maxm;i++)
{
dp[0][0][i]=0;
s[i]=cal(i);
}
for(int i=1;i<=n;i++)
for(int j=0;j<maxm;j++)
for(int k=0;k<maxm;k++)
if(dp[i-1][j][k]!=-1)
for(int l=0;l<maxm;l++)
if(check(k,j,l))
dp[i][k][l]=max(dp[i][k][l],dp[i-1][j][k]+s[k]);
for(int i=0;i<maxm;i++)
ans=max(ans,dp[n][i][0]);
printf("%d
",ans);
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
