포병 진지 상태 압축 dp
13922 단어 poj
dp[now][j][k]=max(dp[now][j][k],dp[pre][k][r]+num[i][j][1]).num[i][j][1]은 i행의 j개 상태의 1의 개수를 나타낸다.이전 조건은!(num[i][j][0]&num[i-1][k][0])&&!(num[i][j][0]&num[i-2][r][0])&&!(num[i-1][k][0] &num[i-2][r][0])는 진실이다.
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define Maxn 1010
using namespace std;
int dp[2][Maxn][Maxn],now,pre,num[110][Maxn][2],cnt1,cnt2,cnt3,graphic[110][11],n,m;
void dfs(int u,int j,int f)
{
int i;
if(j==m)
{
int sum,cc;
sum=cc=0;
for(i=m;i>=1;i--)
{
sum+=graphic[u][i]*(1<<(m-i));
if(graphic[u][i])
cc++;
}
if(f<=2)
{
if(graphic[u][j])
{
if(sum!=1)
{
num[u][++cnt1][0]=sum-1;
num[u][cnt1][1]=cc-1;
}
}
else
{
num[u][++cnt1][0]=sum;
num[u][cnt1][1]=cc;
}
}
else
{
if(graphic[u][j])
{
if(sum!=1)
{
num[u][++cnt1][0]=sum-1;
num[u][cnt1][1]=cc-1;
}
num[u][++cnt1][0]=sum;
num[u][cnt1][1]=cc;
}
else
{
num[u][++cnt1][0]=sum;
num[u][cnt1][1]=cc;
}
}
return ;
}
if(f<=2)
{
if(graphic[u][j]==1)
{
graphic[u][j]=0;
dfs(u,j+1,f+1);
graphic[u][j]=1;
}
else
dfs(u,j+1,f+1);
}
else
{
if(graphic[u][j])
{
dfs(u,j+1,1);
graphic[u][j]=0;
dfs(u,j+1,f+1);
graphic[u][j]=1;
}
else
dfs(u,j+1,f+1);
}
}
void out(int x)
{
if(x==1||x==0)
{
printf("%d",x);
return ;
}
int temp=x%2;
out(x/2);
printf("%d",temp);
}
int main()
{
int i,j,k,r;
char str[20];
memset(graphic,0,sizeof(graphic));
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,0,sizeof(dp));
memset(num,0,sizeof(num));
memset(graphic,0,sizeof(graphic));
for(i=1;i<=n;i++)
{
scanf("%s",&str);
for(j=0;j<m;j++)
{
if(str[j]=='P')
graphic[i][j+1]=1;
else
graphic[i][j+1]=0;
}
}
dfs(1,1,3);
cnt2=cnt1;
cnt1=0;
dfs(2,1,3);
now=1,pre=0;
for(i=1;i<=cnt2;i++)
for(j=1;j<=cnt1;j++)
{
if(!(num[1][i][0]&num[2][j][0]))
dp[now][j][i]=num[1][i][1]+num[2][j][1];
}
for(i=3;i<=n;i++)
{
cnt3=cnt2,cnt2=cnt1,cnt1=0;
dfs(i,1,3);
now=!now,pre=!pre;
for(j=1;j<=cnt1;j++)
for(k=1;k<=cnt2;k++)
for(r=1;r<=cnt3;r++)
{
if(!(num[i][j][0]&num[i-1][k][0])&&!(num[i][j][0]&num[i-2][r][0])&&!(num[i-1][k][0]&num[i-2][r][0]))
dp[now][j][k]=max(dp[now][j][k],dp[pre][k][r]+num[i][j][1]);
}
}
int ans=0;
for(i=1;i<=cnt1;i++)
for(j=1;j<=cnt2;j++)
{
ans=max(ans,dp[now][i][j]);
}
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.