程序厌氧全TLE怎么办???
查看原帖
程序厌氧全TLE怎么办???
817044
cjwdyzxfblzs楼主2023/6/24 16:10

大家帮我看看为啥厌氧呀???

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N = 100;
struct node 
{   int id, sum; 
    bool operator<(const node &S)const { sum < S.sum; }
} cou[N];
int f[N][N], s[N][N], idx;
bool leng[N][N], wide[N][N], sq[N][N];
inline void init()
{
    memset(leng, true, sizeof(leng));
    memset(wide, true, sizeof(wide));
    memset(sq, true, sizeof(sq));
    for (int i = 1; i <= 9; i ++ ) cou[i].id = i;
}
inline int get(int i, int j)
{
    if (i == 5 and j == 5) return 10;
    else if (i >= 4 and j >= 4 and i <= 6 and j <= 6) return 9;
    else if (i >= 3 and i <= 7 and j >= 3 and j <= 7) return 8;
    else if (i >= 2 and i <= 8 and j >= 2 and j <= 8) return 7;
    else return 6;
    return -1;
}
inline int P(int i,int j)
{
    if (i <= 3)
    {   if (j <= 3)         return 1;
        else if (j <= 6)    return 2;
        else                return 3; }
    else if (i <= 6)
    {   if (j <= 3)         return 4;
        else if (j <= 6)    return 5;
        else                return 6; }
    else
    {   if (j <= 3)         return 7;
        else if (j <= 6)    return 8;
        else                return 9; }
    return -1;
}
int res = EOF;
void DFS(int p, int score)
{
    if (p == idx)
    {
        res = max(res, score); return;
    }
    for (int i = 1; i <= 9; i ++ )
        if (leng[ s[p][0] ][i] and wide[ s[p][1] ][i] and sq[ s[p][3] ][i])
        {
            leng[ s[p][0] ][i] = false;
            wide[ s[p][1] ][i] = false;
            sq[ s[p][3] ][i] = false;
            DFS(p + 1, score + (s[p][2] * i));
            leng[ s[p][0] ][i] = true;
            wide[ s[p][1] ][i] = true;
            sq[ s[p][3] ][i] = true;
        }
}
int sum;
signed main()
{
    init();
    for (int i = 1; i <= 9; i ++ )
    {
        for (int j = 1; j <= 9; j ++ )
        {
            f[i][j] = read();
            if (f[i][j] > 0)
            {
                leng[i][ f[i][j] ] = false;
                wide[j][ f[i][j] ] = false;
                sq[(i - 1) / 3 * 3 + (j - 1) / 3 + 1][ f[i][j] ] = false;
                sum += f[i][j] * get(i, j);
            }
            else cou[i].sum ++ ;
        }
    }
    sort(cou + 1, cou + 9 + 1);
    for (int i = 1; i <= 9; i ++ )
        for (int j = 1; j <= 9; j ++ )
            if (f[cou[i].id][j] == 0)   
                s[idx][0] = cou[i].id,                  // ——
                s[idx][1] = j,                          // |
                s[idx][2] = get(cou[i].id, j),          // score
                s[idx ++ ][3] = P(cou[i].id, j);        // position
    DFS(0, sum);
    cout << res << endl;
    return 0;
}

// 核心优化 : 某一行的 0 较少,先确定某一行
2023/6/24 16:10
加载中...