求助记忆化搜索tle
  • 板块P1436 棋盘分割
  • 楼主sycqwq
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/11/27 18:46
  • 上次更新2023/11/3 23:26:20
查看原帖
求助记忆化搜索tle
151647
sycqwq楼主2021/11/27 18:46

为啥会t啊

我不理解

复杂度是对的啊

#include<bits/stdc++.h>
#define int long long
#define inf 9187201950435737471
using namespace std;
int n=8,f[10][10][10][10][20],a[105][105],k,sum[10][10][10][10];
int solve(int x,int y,int x1,int y1,int k)
{
    if(f[x][y][x1][y1][k]!=inf)
        return f[x][y][x1][y1][k];
    for(int i=x;i<x1;i++)
    {
        f[x][y][x1][y1][k]=min(f[x][y][x1][y1][k],min(solve(x,y,i,y1,k-1)+solve(i+1,y,x1,y1,0),solve(x,y,i,y1,0)+solve(i+1,y,x1,y1,k-1)));
    }
    for(int i=y;i<y1;i++)
    {
        f[x][y][x1][y1][k]=min(f[x][y][x1][y1][k],min(solve(x,y,x1,i,k-1)+solve(x,i+1,x1,y1,0),solve(x,y,x1,i,0)+solve(x,i+1,x1,y1,k-1)));
    }
    // cout<<"####"<<x<<' '<<y<<' '<<x1<<' '<<y1<<' '<<f[x][y][x1][y1][k]<<endl;
    return f[x][y][x1][y1][k];
}
signed main()
{
    cin>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                    for(int l=1;l<=n;l++)
                    {
                        for(int qaq=min(i,k);qaq<=max(i,k);qaq++)
                            for(int qwq=min(j,l);qwq<=max(j,l);qwq++)
                                sum[i][j][k][l]+=a[qaq][qwq];
                        sum[i][j][k][l]*=sum[i][j][k][l];
                    }
    }
    memset(f,0x7f,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                for(int l=1;l<=n;l++)
                {
                    f[i][j][k][l][0]=sum[i][j][k][l];
                    // cout<<i<<' '<<j<<' '<<k<<' '<<l<<' '<<f[i][j][k][l][0]<<endl;
                }
    // cout<<f[1][1][1][1][1]<<endl;
    cout<<solve(1,1,n,n,k-1);
    return 0;
}
2021/11/27 18:46
加载中...