admin 管理员组

文章数量: 887006

[HNOI2007]神奇游乐园

Description：

在方格图上找一条回路使经过的权值最小

Hint：

\(n<=100,m<=6\)

Solution:

一开始又看错题了。。。稍有细节的水题，详见代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn=102,c[4]={0,-1,1,0};
struct data {int key; ll val;
};
int n,m,t,ex,ey;
int g[mxn][mxn];
char mp[mxn][mxn];
ll ans=-100000000;
unordered_map<int ,data > dp[3];
map<int , int > vis; 
typedef unordered_map<int ,data >::iterator uit;inline void copy(data x,int id) {dp[id][x.key<<2]=(data){x.key<<2,x.val};}inline int get(int st,int x) {x<<=1; return (st>>x)&3;}
inline int md(int st,int x,int val) {x<<=1; return (st&(~(3<<x)))|(val<<x);}inline int getl(int st,int x) {int l=x,cnt=1;while(cnt!=0) cnt+=c[get(st,--l)];return l;
}inline int getr(int st,int x) {int r=x,cnt=-1;while(cnt!=0) cnt+=c[get(st,++r)];return r;
}inline void update(int x,int y,data d) 
{int st=d.key; ll val=d.val;int p=get(st,y),q=get(st,y+1);if(p==0&&q==0) {if(vis[st]) dp[t^1][st]=(data){st,max(dp[t^1][st].val,val)};else dp[t^1][st]=(data){st,val},vis[st]=1;if(x==n-1||y==m-1) return ;int nst=md(st,y,1); nst=md(nst,y+1,2);if(vis[nst]) dp[t^1][nst]=(data){nst,max(dp[t^1][nst].val,val+g[x][y])}; //由于map不能赋初值，故另外使用vis来记录状态有无else dp[t^1][nst]=(data){nst,val+g[x][y]},vis[nst]=1;return ; //不要少写return}if(p==0||q==0) {if(y<m-1) {int nst=md(st,y,0); nst=md(nst,y+1,p+q);if(vis[nst]) dp[t^1][nst]=(data){nst,max(dp[t^1][nst].val,val+g[x][y])};else dp[t^1][nst]=(data){nst,val+g[x][y]},vis[nst]=1;}if(x<n-1) {int nst=md(st,y,p+q); nst=md(nst,y+1,0);if(vis[nst]) dp[t^1][nst]=(data){nst,max(dp[t^1][nst].val,val+g[x][y])};else dp[t^1][nst]=(data){nst,val+g[x][y]},vis[nst]=1;}return ;}int nst=md(st,y,0); nst=md(nst,y+1,0);if(p==1&&q==1) nst=md(nst,getr(st,y+1),1);if(p==2&&q==2) nst=md(nst,getl(st,y),2);if(p==1&&q==2) {st=md(st,y,0),st=md(st,y+1,0);if(!st)  //为了保证只有一条路径ans=max(ans,val+g[x][y]);return ;} if(vis[nst]) dp[t^1][nst]=(data){nst,max(dp[t^1][nst].val,val+g[x][y])};else dp[t^1][nst]=(data){nst,val+g[x][y]},vis[nst]=1;
}int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;++i) for(int j=0;j<m;++j)scanf("%d",&g[i][j]);for(int i=0;i<n;++i) for(int j=0;j<m;++j) mp[i][j]='.';ex=n-1,ey=m-1;      t=0; dp[t][0]=(data){0,0}; for(int i=0;i<n;++i) {dp[2].clear();for(uit j=dp[t].begin();j!=dp[t].end();++j) copy((*j).second,2);dp[t].clear();for(uit j=dp[2].begin();j!=dp[2].end();++j) dp[t][(*j).second.key]=(*j).second; for(int j=0;j<m;++j) {dp[t^1].clear(); vis.clear();for(uit k=dp[t].begin();k!=dp[t].end();++k) update(i,j,(*k).second);t^=1;}}printf("%lld",ans);return 0;
}

转载于:.html

本文标签： HNOI2007神奇游乐园

版权声明：本文标题：[HNOI2007]神奇游乐园 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732362241h1535542.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。