플러그 dp의 몇 개의 템플릿
13707 단어 동적 기획
/*
ural1519
, ,
*/
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#define LL long long
using namespace std;
const int maxn=30001;
int n,m,now,pre;
int mov[13]={0,2,4,6,8,10,12,14,16,18,20,22,24};//
char gp[20][20],fx,fy;// ,
inline int getbit(LL st,int k){ return (st>>mov[k])&3;}// k
inline int pybit(LL st,int k){ return st<<mov[k];} // k
inline LL clrbit(LL st,int i,int j){ return st&(~(3<<mov[i]))&(~(3<<mov[j]));}// i j
struct node// hash
{
int head[maxn],next[maxn],size;
LL sum[maxn],sta[maxn];//
void clear()
{
memset(head,-1,sizeof(head));
memset(sum,0,sizeof(sum));
size=0;
}
void push(LL st,const LL v)
{
LL hash=st%maxn;
for(int i=head[hash];i>=0;i=next[i])
{
if(sta[i]==st)
{
sum[i]+=v;
return;
}
}
sta[size]=st,sum[size]=v;
next[size]=head[hash],head[hash]=size++;
}
}dp[2];
inline int fl(LL st,int pos)// pos
{
int cnt=1;
for(int i=pos+1;i<=m;i++)
{
int k=getbit(st,i);
if(k==1) cnt++;
else if(k==2) cnt--;
if(!cnt) return i;
}
}
inline int fr(LL st,int pos)// pos
{
int cnt=1;
for(int i=pos-1;i>=0;i--)
{
int k=getbit(st,i);
if(k==2) cnt++;
else if(k==1) cnt--;
if(!cnt) return i;
}
}
void DP(int x,int y,int k)// ,
{
int l=getbit(dp[pre].sta[k],y-1);
int up=getbit(dp[pre].sta[k],y);
LL st=clrbit(dp[pre].sta[k],y-1,y);
LL v=dp[pre].sum[k];
if(!l&&!up)
{
if(gp[x][y]=='*')
{
dp[now].push(st,v);
return;
}
if(x<n&&y<m&&gp[x+1][y]=='.'&&gp[x][y+1]=='.')
dp[now].push(st|pybit(1,y-1)|pybit(2,y),v);
}
else if(!l||!up)
{
int e=l+up;
if(x<n&&gp[x+1][y]=='.')
dp[now].push(st|pybit(e,y-1),v);
if(y<m&&gp[x][y+1]=='.')
dp[now].push(st|pybit(e,y),v);
}
else if(l==1&&up==1)
dp[now].push(st^pybit(3,fl(st,y)),v);
else if(l==2&&up==2)
dp[now].push(st^pybit(3,fr(st,y-1)),v);
else if(l==2&&up==1)
dp[now].push(st,v);
else if(x==fx&&y==fy)
dp[now].push(st,v);
}
LL solve()
{
dp[0].clear();//
dp[0].push(0,1);
now=0,pre=1;
for(int i=1;i<=n;i++)//
{
pre=now,now^=1,dp[now].clear();
for(int k=0;k<dp[pre].size;k++)//
dp[now].push(pybit(dp[pre].sta[k],1),dp[pre].sum[k]);
for(int j=1;j<=m;j++)
{
pre=now,now^=1,dp[now].clear();
for(int k=0;k<dp[pre].size;k++)
{
DP(i,j,k);
}
}
}
for(int i=0;i<dp[now].size;i++)//
if(dp[now].sta[i]==0)
return dp[now].sum[i];
return 0;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=n;i++)// 1
scanf("%s",&gp[i][1]);
fx=0;
for(int i=n;i>0&&!fx;i--)//
{
for(int j=m;j>0&&!fx;j--)
{
if(gp[i][j]=='.')
fx=i,fy=j;
}
}
if(fx==0) puts("0");
else cout<<solve()<<endl;
}
return 0;
}
/*
ural1519
,
*/
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int maxn=30001,inc=3,bit=7;//3 111
int n,m,now,pre,code[20],bin[20],res[20];//
char gp[20][20],fx,fy;//
struct node// hash
{
int head[maxn],next[maxn],size;
LL sum[maxn],sta[maxn];
void clear()
{
memset(head,-1,sizeof(head));
size=0;
}
void push(LL st,const LL v)
{
LL hash=st%maxn;
for(int i=head[hash];i>=0;i=next[i])
{
if(sta[i]==st)
{
sum[i]+=v;
return ;
}
}
sta[size]=st,sum[size]=v;
next[size]=head[hash],head[hash]=size++;
}
}dp[2];
inline LL encode(int m)// code
{
LL st=0;
int cnt=1;
memset(bin,-1,sizeof(bin));
bin[0]=0;
for(int i=m;i>=0;i--)
{
if(bin[code[i]]==-1)
bin[code[i]]=cnt++;
code[i]=bin[code[i]];
st<<=inc;
st|=code[i];
}
return st;
}
inline void decode(LL st,int m)// code
{
for(int i=0;i<=m;i++)
{
code[i]=st&bit;
st>>=inc;
}
}
void DP(int x,int y,int k)//dp
{
decode(dp[pre].sta[k],m);
int l=code[y-1];
int up=code[y];
code[y-1]=code[y]=0;
memcpy(res,code,sizeof(code));
LL v=dp[pre].sum[k];
if(!l&&!up)
{
if(gp[x][y]=='*')
dp[now].push(encode(m),v);
else if(x<n&&y<m&&gp[x+1][y]=='.'&&gp[x][y+1]=='.')
{
code[y]=code[y-1]=bit;
dp[now].push(encode(m),v);
}
}
else if(!l||!up)
{
int e=l+up;
if(x<n&&gp[x+1][y]=='.')
{
code[y-1]=e;
dp[now].push(encode(m),v);
memcpy(code,res,sizeof(res));
}
if(y<m&&gp[x][y+1]=='.')
{
code[y]=e;
dp[now].push(encode(m),v);
}
}
else if(l!=up)
{
for(int i=0;i<=m;i++)
if(code[i]==up)
code[i]=l;
dp[now].push(encode(m),v);
}
else if(x==fx&&y==fy)
dp[now].push(encode(m),v);
}
LL solve()
{
dp[0].clear();//
dp[0].push(0,1);
now=0,pre=1;
for(int i=1;i<=n;i++)//
{
pre=now,now^=1,dp[now].clear();
for(int k=0;k<dp[pre].size;k++)//
dp[now].push(dp[pre].sta[k]<<inc,dp[pre].sum[k]);
for(int j=1;j<=m;j++)
{
pre=now,now^=1,dp[now].clear();
for(int k=0;k<dp[pre].size;k++)
{
DP(i,j,k);
}
}
}
for(int i=0;i<dp[now].size;i++)
if(dp[now].sta[i]==0)
return dp[now].sum[i];
return 0;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=n;i++)// 1
scanf("%s",&gp[i][1]);
fx=fy=0;
for(int i=n;i>0&&!fx;i--)//
for(int j=m;j>0&!fx;j--)
if(gp[i][j]=='.')
fx=i,fy=j;
if(fx==0)puts("0");
else cout<<solve()<<endl;
}
}
/*
zoj 3213 Beautiful Meadow
, .
, (3), ,
*/
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iostream>
#define LL long long
using namespace std;
const int maxn=30001,INF=1<<30;
int mov[10]={0,2,4,6,8,10,12,14,16,18};
struct node
{
int size,head[maxn],next[maxn];
LL sta[maxn],sum[maxn];
void clear()
{
memset(head,-1,sizeof(head));
size=0;
}
void push(LL st,const LL v)
{
LL hash=st%maxn;
for(int i=head[hash];i>=0;i=next[i])
{
if(sta[i]==st)
{
sum[i]=max(sum[i],v);
return ;
}
}
sta[size]=st,sum[size]=v;
next[size]=head[hash],head[hash]=size++;
}
}dp[2];
inline int getbit(LL st,int k){return 3&(st>>mov[k]);}
inline int pybit(LL st,int k){return st<<mov[k];}
inline int clrbit(LL st,int a,int b){return st&(~(3<<mov[a]))&(~(3<<mov[b]));}
int fl(LL st,int k,int m)
{
int cnt=1;
for(int i=k+1;i<=m;i++)
{
int e=getbit(st,i);
if(e==2) cnt--;
else if(e==1) cnt++;
if(!cnt) return i;
}
}
int fr(LL st,int k)
{
int cnt=1;
for(int i=k-1;i>=0;i--)
{
int e=getbit(st,i);
if(e==2) cnt++;
else if(e==1) cnt--;
if(!cnt) return i;
}
}
int count(LL st)//
{
int cnt=0;
while(st)
{
if(getbit(st,0)==3)
cnt++;
st>>=2;
}
return cnt;
}
int n,m,gp[20][20];
LL DP()
{
LL ans=-INF;
dp[0].clear();
dp[0].push(0,0);
int now=0,pre=1;
for(int i=1;i<=n;i++)
{
pre=now,now^=1,dp[now].clear();
for(int j=0;j<dp[pre].size;j++)
dp[now].push(dp[pre].sta[j]<<2,dp[pre].sum[j]);
for(int j=1;j<=m;j++)
{
if(gp[i][j]!=0) ans=max(ans,(LL)gp[i][j]);
pre=now,now^=1,dp[now].clear();
for(int k=0;k<dp[pre].size;k++)
{
LL l=getbit(dp[pre].sta[k],j-1);
LL up=getbit(dp[pre].sta[k],j);
LL st=clrbit(dp[pre].sta[k],j,j-1);
LL v=dp[pre].sum[k]+gp[i][j];
if(!l&&!up)
{
dp[now].push(st,dp[pre].sum[k]);
if(gp[i][j]==0)
continue;
if(i<n&&j<m&&gp[i+1][j]&&gp[i][j+1])
dp[now].push(st|pybit(1,j-1)|pybit(2,j),v);
if(count(st)<=1)
{
if(i<n&&gp[i+1][j])
dp[now].push(st|pybit(3,j-1),v);
if(j<m&&gp[i][j+1])
dp[now].push(st|pybit(3,j),v);
}
}
else if(!l||!up)
{
int e=l+up;
if(i<n&&gp[i+1][j])
dp[now].push(st|pybit(e,j-1),v);
if(j<m&&gp[i][j+1])
dp[now].push(st|pybit(e,j),v);
if(e!=3&&count(st)<=1)
{
if(e==1) dp[now].push(st|pybit(3,fl(st,j,m)),v);
else dp[now].push(st|pybit(3,fr(st,j-1)),v);
}
else if(e==3&&st==0)
ans=max(ans,v);
}
else if(l==up)
{
if(l==1)
dp[now].push(st^pybit(3,fl(st,j,m)),v);
if(l==2)
dp[now].push(st^pybit(3,fr(st,j-1)),v);
if(l==3)
ans=max(ans,v);
}
else if(l==2&&j==1) dp[now].push(st,v);
else if(l==3||up==3)
{
int e=l==3?up:l;
if(e==1)
dp[now].push(st|pybit(3,fl(st,j,m)),v);
if(e==2)
dp[now].push(st|pybit(3,fr(st,j-1)),v);
}
}
}
}
if(ans==-INF)
ans=0;
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&gp[i][j]);
cout<<DP()<<endl;
}
return 0;
}
/*
uva10572 black&white
, , , 4
.
, , (m), (m+1).
____———— , .
.
*/
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=10007,bit=7,inc=3;
int pre[9][9][maxn];//
bool res[9][9][maxn];//
int bin[20],code[20];
struct node
{
int size,head[maxn],next[maxn];
LL sta[maxn],clo[maxn],sum[maxn];
void clear()
{
memset(head,-1,sizeof(head));
size=0;
}
void push(LL st,const LL v,LL cs,int x,int y,bool cl,int k)
{
int hash=((st*13)+cs)%maxn;
for(int i=head[hash];i>=0;i=next[i])
{
if(sta[i]==st&&clo[i]==cs)
{
sum[i]+=v;
return ;
}
}
sta[size]=st,clo[size]=cs,sum[size]=v;
res[x][y][size]=cl,pre[x][y][size]=k;
next[size]=head[hash],head[hash]=size++;
}
}dp[2];
LL encode(int m)// 0 , m
{
LL st=0,cnt=0;
memset(bin,-1,sizeof(bin));
for(int i=m-1;i>=0;i--)
{
if(bin[code[i]]==-1)
bin[code[i]]=cnt++;
code[i]=bin[code[i]];
st<<=inc;
st|=code[i];
}
return st;
}
void decode(LL st,int m)
{
for(int i=0;i<m;i++)
{
code[i]=st&bit;
st>>=inc;
}
}
int n,m,now,old;
char gp[20][20];
bool check(LL cs,int x,int y,int m,int nc)//
{
int cnt=0,cnt1=0;
for(int i=0;i<m;i++)
{
if(code[i]==code[y])
cnt++;
if(((cs>>i)&1)==(nc^1))
cnt1++;
}
if(cnt==1)
{
if(cnt1>1)
return false;
char ch=nc==1?'o':'#';
for(int i=x-1;i<n;i++)
for(int j=i==x-1?y+1:0;j<m;j++)
{
if(gp[i][j]==ch)
return false;
if(i+1<n&&j+1<m)
return false;
}
}
return true;
}
void DP(int x,int y,int nc)
{
for(int k=0;k<dp[old].size;k++)
{
bool l=y==0?0:((dp[old].clo[k]>>(y-1))&1)==nc;
bool up=x==0?0:((dp[old].clo[k]>>y)&1)==nc;
bool lp=(x==0||y==0)?0:((dp[old].clo[k]>>m)&1)==nc;
decode(dp[old].sta[k],m);
if(x&&!up&&!check(dp[old].clo[k],x,y,m,nc))
continue;
if(!l&&!up&&!lp)
code[y]=10;
else if(l&&!up&&!lp)
code[y]=code[y-1];
else if(!l&&up&&!lp)
code[y]=code[y];
else if(!lp&&l&&up)
{
if(code[y-1]!=code[y])
{
for(int i=0,id=code[y];i<m;i++)
if(code[i]==id)
code[i]=code[y-1];
}
}
else if(lp&&!up&&!l)
{
if(x==n-1&&y==m-1)
continue;
code[y]=10;
}
else if(lp&&l&&!up)
code[y]=code[y-1];
else if(lp&&up&&!l)
code[y]=code[y];
else continue;
LL cs=dp[old].clo[k]&(~(1<<y))&(~(1<<m));
if(nc) cs|=1<<y;
if((up==0&&nc==0)||(up==1&&nc==1)) cs|=1<<m;
dp[now].push(encode(m),dp[old].sum[k],cs,x,y,nc,k);
}
}
void slove()
{
dp[0].clear();
dp[0].push(0,1,0,n,m,0,-1);
now=0,old=1;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
old=now,now^=1,dp[now].clear();
if(gp[i][j]!='#')
DP(i,j,0);
if(gp[i][j]!='o')
DP(i,j,1);
}
int flag=-1,ans=0;
for(int i=0;i<dp[now].size;i++)//
{
decode(dp[now].sta[i],m);
int cnt=0;
memset(bin,-1,sizeof(bin));
for(int j=0;j<m;j++)
{
if(bin[code[j]]==-1)
bin[code[j]]=cnt++;
}
if(cnt<=2)
{
flag=i;
ans+=dp[now].sum[i];
}
}
//
if(flag==-1)
puts("0
");
else
{
printf("%d
",ans);
for(int i=n-1;i>=0;i--)
for(int j=m-1;j>=0;j--)
{
gp[i][j]=res[i][j][flag]==0?'o':'#';
flag=pre[i][j][flag];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
printf("%c",gp[i][j]);
puts("");
}
puts("");
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%s",gp[i]);
}
slove();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
