AGC033D Complexity

本文主要是介绍AGC033D Complexity，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
如果直接DP设$f[i][j][k][l]$记录矩形，瓶颈在于状态数上。
考虑减少状态数，其实也是一个比较套路的方法，发现答是$log$级别的，于是把其中一维状态改为答案，DP值改为那维状态，转移时考虑横着还是竖着切，一边直接用上一个转，一边利用单调性转即可，效率$O(n^{3}logn)$。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,m,f[2][N][N][N],a[N][N];
bool check(int j,int k,int l,int r){int x=(k-j+1)*(r-l+1),y=a[k][r]-a[j-1][r]-a[k][l-1]+a[j-1][l-1];return (!y || x==y);
}
int main()
{//freopen(".in","r",stdin);//freopen(".out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){char c; scanf(" %c",&c);a[i][j]=(c=='#')+a[i-1][j]+a[i][j-1]-a[i-1][j-1];}for(int x=0;x<2;x++) for(int j=1;j<=n+1;j++)for(int l=1;l<=m;l++) f[x][j][j-1][l]=N;for(int j=1;j<=n;j++) for(int k=j;k<=n;k++){for(int l=m;l;l--){if(l==m) f[0][j][k][l]=m;else f[0][j][k][l]=f[0][j][k][l+1];while(!check(j,k,l,f[0][j][k][l])) f[0][j][k][l]--;//cout<<j<<" "<<k<<" "<<l<<" "<<f[0][j][k][l]<<endl;}}//return 0;for(int i=1;;i++){int x=(i&1);if(f[!x][1][n][1]==m){cout<<i-1<<endl; return 0;}for(int j=1;j<=n;j++) for(int k=j;k<=n;k++)for(int l=1;l<=m;l++) f[x][j][k][l]=f[!x][j][k][f[!x][j][k][l]+1];for(int j=1;j<=n;j++) for(int l=1;l<=m;l++){for(int k=j,p=j;k<=n;k++){while(p<k && min(f[!x][j][p][l],f[!x][p+1][k][l])<=min(f[!x][j][p+1][l],f[!x][p+2][k][l])) p++;f[x][j][k][l]=max(f[x][j][k][l],min(f[!x][j][p][l],f[!x][p+1][k][l]));}}}return 0;
}

这篇关于AGC033D Complexity的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---