首页 > 代码库 > BZOJ 3111: [Zjoi2013]蚂蚁寻路
BZOJ 3111: [Zjoi2013]蚂蚁寻路
Sol
DP.
首先观察转折,画画图,看看移动路线,可以非常轻易的发现如果走到起点的下方是回不去的..
然后它就相当于一个底部是平的,顶部凹凹凸凸的形状,每右转两次或左转两次就会形成小矩阵,这样就可以来DP了.
首先一个非常简单的思路,就是f[k][i][j]表示取到第j列高度为h最大权值,枚举上一个转折点,复杂度 \(O(n^5k)\) 因为上一个点一定是与他同一行的,枚举行,枚举次数,枚举列,枚举高度,枚举上一个位置的列,枚举上一个位置的行.
我们可以优化,让他一次DP一行,其实可以发现就是取高度大于或小于当前高度,列小于当前的点最大值,这个最大值我们可以记录下来然后 \(O(1)\) 转移,再加上每列前缀和,就是 \(O(n^3k)\) 的了.
Code
/************************************************************** Problem: 3111 User: BeiYu Language: C++ Result: Accepted Time:172 ms Memory:1460 kb****************************************************************/ #include<cstdio>#include<cstring>#include<iostream>using namespace std; const int N = 105;const int K = 25;const int INF = 0x3fffffff; int n,m,k,ans;int a[N][N],d[N][N];int f[N][N],g[N][N]; inline int in(int x=0,char ch=getchar(),int v=1){ while(ch!=‘-‘&&(ch>‘9‘||ch<‘0‘)) ch=getchar();if(ch==‘-‘) v=-1,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x*v; }int main(){// freopen("in.in","r",stdin); n=in(),m=in(),k=in();ans=-INF; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=in();// for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) d[i][j]=d[i-1][j]+a[i][j]; for(int i=1;i<=n;i++){ memset(f,0x8f,sizeof(f)),memset(g,0x8f,sizeof(g)),memset(d,0,sizeof(d)); for(int u=1;u<=m;u++) for(int v=i;v;v--) d[v][u]=d[v+1][u]+a[v][u]; for(int u=1;u<=m;u++) for(int v=1;v<=i;v++) g[v][u]=max(g[v][u-1],0)+d[v][u]; for(int q=1;q<=k;q++){ for(int u=1;u<=m;u++) for(int v=1,tmp=-INF;v<=i;v++) tmp=max(tmp,g[v-1][u-1]),f[v][u]=max(f[v][u-1],tmp)+d[v][u]; for(int u=1;u<=m;u++) for(int v=i,tmp=-INF;v;v--) tmp=max(tmp,f[v+1][u-1]),g[v][u]=max(tmp,g[v][u-1])+d[v][u]; } for(int u=1;u<=m;u++) for(int v=1;v<=i;v++) ans=max(ans,g[v][u]); }cout<<ans<<endl; return 0;}
BZOJ 3111: [Zjoi2013]蚂蚁寻路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。