头像

奇点lzy




离线:5天前


最近来访(168)
用户头像
InvolutionZ
用户头像
水木_7
用户头像
幽梦影情结
用户头像
Tiaer
用户头像
Aurora-
用户头像
theshy_6
用户头像
无意秋风
用户头像
你好闹啊
用户头像
米龙
用户头像
五星市民欧某人
用户头像
_魂淡_
用户头像
qut_zh
用户头像
那个小谁
用户头像
j5zslhw
用户头像
XiaozLi.
用户头像
Thaddeus.
用户头像
ZCLiu
用户头像
Eva_0
用户头像
好氧君的菌
用户头像
能不能当你爹了

活动打卡代码 AcWing 321. 棋盘分割

#include<bits/stdc++.h>

using namespace std;

const int N = 15, M  = 9, INF = 1e9;

int n, m = 8;
int s[M][M];
double f[M][M][M][M][N];
double X;

int get_sum(int x1, int y1, int x2, int y2)
{
    return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}

double get(int x1, int y1, int x2, int y2)
{
    double sum = get_sum(x1, y1, x2, y2) - X;
    return (double) sum * sum / n;
}

double dp(int x1, int y1, int x2, int y2, int k)
{
    double &v = f[x1][y1][x2][y2][k];
    if(v >= 0) return v;
    if(k == 1) return v = get(x1, y1, x2, y2);

    v = INF;

    for(int i=x1;i<x2;i++)
    {
        v = min(v, get(x1, y1, i, y2) + dp(i + 1, y1, x2, y2, k - 1));
        v = min(v, get(i + 1, y1, x2, y2) + dp(x1, y1, i , y2, k - 1));
    }

    for(int i=y1;i<y2;i++)
    {
        v = min(v, get(x1, y1, x2, i) + dp(x1, i + 1, x2, y2, k - 1));
        v = min(v, get(x1, i + 1, x2 ,y2) + dp(x1, y1, x2, i, k - 1));
    }

    return v;

}

int main()
{
    cin>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>s[i][j];
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }

    X = (double) s[m][m] / n;

    memset(f, -1, sizeof f);

    printf("%.3lf\n", sqrt(dp(1, 1, 8, 8, n)));

    return 0;
}


活动打卡代码 AcWing 479. 加分二叉树

奇点lzy
10天前
#include<bits/stdc++.h>

using namespace std;

const int N = 30;

int n;
int w[N];
int f[N][N],g[N][N];

void dfs(int l, int r)
{
    if(l > r) return;
    int k = g[l][r];
    cout << k << ' ';
    dfs(l, k - 1);
    dfs(k + 1, r);
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];

    for(int len=1;len<=n;len++)
        for(int l=1;l+len-1<=n;l++)
        {
            int r = l + len - 1;
            if(l == r) f[l][r] = w[l], g[l][r] = l;
            else
            {
                for(int k=l;k<=r;k++)
                {
                    int left = k == l ? 1 : f[l][k - 1];
                    int right = k == r ? 1 : f[k + 1][r];
                    int score = left * right + w[k];
                    if(f[l][r] < score)
                    {
                        f[l][r] = score;
                        g[l][r] = k;
                    }
                }
            }
        }

        cout << f[1][n] << endl;

        dfs(1, n);

    return 0;
}



奇点lzy
11天前
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 55, M = 35, INF = 1e9;

int n;
int w[N];
LL f[N][N][M];

void add(LL a[], LL b[])
{
    static LL c[M];
    memset(c, 0, sizeof c);
    for(int i=0, t=0;i<M;i++)
    {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}

void mul(LL a[], LL b)
{
    static LL c[M];
    memset(c, 0, sizeof c);
    LL t = 0;
    for(int i=0;i<M;i++)
    {
        t += a[i] * b;
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}

int cmp(LL a[], LL b[])
{
    for(int i=M-1;i>=0;i--)
        if(a[i] > b[i]) return 1;
        else if(a[i] < b[i]) return -1;
    return 0;
}

void print(LL a[])
{
    int k = M - 1;
    while(k && !a[k]) k --;
    while(k >= 0) cout << a[k --];
    cout << endl;
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++) cin>>w[i];


    LL temp[M];
    for(int len=3;len<=n;len++)
        for(int l=1;l+len-1<=n;l++)
        {
            int r = l + len - 1;
            f[l][r][M - 1] = 1;
            for(int k=l+1;k<r;k++)
            {
                memset(temp, 0, sizeof temp);
                temp[0] = w[l];
                mul(temp, w[k]);
                mul(temp, w[r]);
                add(temp, f[l][k]);
                add(temp, f[k][r]);
                if(cmp(f[l][r], temp) > 0)
                    memcpy(f[l][r], temp, sizeof temp);
            }
            //f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
        }

    print(f[1][n]);

    return 0;
}


活动打卡代码 AcWing 320. 能量项链

奇点lzy
17天前
#include<bits/stdc++.h>

using namespace std;

const int N = 210;

int n;
int w[N];
int f[N][N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        w[i + n] = w[i];
    }

    for(int len =3;len<=n+1;len++)
    {
        for(int l=1;l+len-1<=n*2;l++)
        {
            int r = l + len - 1;
            for(int k=l+1;k<r;k++)
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
        }
    }

    int maxv = 0;

    for(int i=1;i<=n*2;i++)
    {
        maxv = max(maxv, f[i][i + n]);
    }

    cout << maxv << endl;

    return 0;
}


活动打卡代码 AcWing 1068. 环形石子合并

奇点lzy
17天前
#include<bits/stdc++.h>

using namespace std;

const int N = 410, INF = 0x3f3f3f3f;

int n;
int s[N],w[N];
int f[N][N],g[N][N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        w[i + n] = w[i];
    }

    for(int i=1;i<=n*2;i++) s[i] = s[i - 1] + w[i];

    memset(f, 0x3f, sizeof f);
    memset(g, -0x3f, sizeof g);

    for(int len=1;len<=n;len++)
    {
        for(int l=1;l+len-1<=n*2;l++)
        {
            int r = l + len - 1;
            if(len == 1) f[l][r] = g[l][r] = 0;
            else
            {
                for(int k=l;k<r;k++)
                {
                    f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                    g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
                }
            }
        }
    }

    int maxv = -INF, minv = INF;

    for(int i=1;i<=n;i++)
    {
        maxv = max(maxv, g[i][i + n - 1]);
        minv = min(minv, f[i][i + n - 1]);
    }

    cout << minv << endl << maxv << endl;

    return 0;
}


活动打卡代码 AcWing 524. 愤怒的小鸟

奇点lzy
18天前
#include<bits/stdc++.h>

using namespace std;

typedef pair<double, double> PDD;

#define x first
#define y second

const int N = 18, M = 1 << 18;
const double eps = 1e-8;

int n,m;
PDD q[N];
int path[N][N];
int f[M];

int cmp(double x, double y)
{
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}

int main()
{
    int T;
    cin>>T;

    while(T --)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>q[i].x>>q[i].y;

        memset(path, 0 ,sizeof path);
        for(int i=0;i<n;i++)
        {
            path[i][i] = 1 << i;
            for(int j=0;j<n;j++)
            {
                double x1 = q[i].x, y1 = q[i].y;
                double x2 = q[j].x, y2 = q[j].y;

                if(!cmp(x1, x2)) continue;

                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 - a * x1;

                if(cmp(a, 0) >= 0) continue;

                int state = 0;
                for(int k=0;k<n;k++)
                {
                    double x = q[k].x, y = q[k].y;
                    if(!cmp(a * x * x + b * x, y)) state += 1 << k;
                }

                path[i][j] = state;

            }
        }

        memset(f, 0x3f, sizeof f);
        f[0] = 0;

        for(int i=0;i+1<1<<n;i++)
        {
            int x = 0;
            for(int j=0;j<n;j++)
                if(!(i >> j & 1))
                {
                    x = j;
                    break;
                }

            for(int j=0;j<n;j++)
                f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
        }

    cout << f[(1 << n) - 1] << endl;    

    }

    return 0;
}


活动打卡代码 AcWing 4719. 商品种类

奇点lzy
18天前
#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin>>n;

    unordered_set<string> hash;

    while(n --)
    {
        string a,b;
        cin>>a>>b;
        hash.insert(a + ' ' + b);
    }

    cout << hash.size() << endl;
    return 0;
}


活动打卡代码 AcWing 292. 炮兵阵地

奇点lzy
1个月前
#include<bits/stdc++.h>

using namespace std;

const int N = 10, M = 1 << 10;

int n,m;
int g[1010];
int f[2][M][M]; //f[i][j][k] 第i行的状态是k,上一行的状态是j
vector<int> state;
int cnt[M];

bool check(int state)
{
    for(int i=0;i<m;i++)
        if((state >> i & 1) && ((state >> i + 1 & 1) || (state >> i + 2 & 1)))
            return false;
    return true;        
}

int count(int state)
{
    int res = 0;
    for(int i=0;i<m;i++)
        if(state >> i & 1)
            res ++;
    return res;        
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
        {
            char c;
            cin>>c;
            g[i] += (c == 'H') << j;
        }

    for(int i=0;i<1<<m;i++)
        if(check(i))
        {
            state.push_back(i);
            cnt[i] = count(i);
        }

    for(int i=1;i<=n+2;i++)
        for(int j=0;j<state.size();j++)//第i-1行状态
            for(int k=0;k<state.size();k++)//第i行状态
                for(int u=0;u<state.size();u++)//第i-2行状态
                {
                    int a = state[j], b = state[k], c = state[u];
                    if((a & b) | (a & c) | (b & c)) continue;
                    if(g[i] & b | g[i - 1] & a) continue;
                    f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
                }

    cout << f[n + 2 & 1][0][0] << endl;

    return 0;
}


活动打卡代码 AcWing 327. 玉米田

奇点lzy
1个月前
#include<bits/stdc++.h>

using namespace std;

const int N = 14, M = 1 << 12, mod = 1e8;

int n,m;
int g[N];
vector<int> head[M];
vector<int> state;
int f[N][M];   //f[i][s]表示已经种植前i行,且第i行种植的状态为s的方案数

bool check(int state)
{
    for(int i=0;i+1<m;i++)
        if((state >> i & 1) && (state >> i + 1 & 1))
            return false;
    return true;        
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
        {
            int t;
            cin>>t;
            g[i] += !t * (1 << j);
        }

    for(int i=0;i<1<<m;i++)
        if(check(i))
            state.push_back(i);

    for(int i=0;i<state.size();i++)
        for(int j=0;j<state.size();j++)
        {
            int a = state[i], b = state[j];
            if(!(a & b))
                head[i].push_back(j);
        }

    f[0][0] = 1;
    for(int i=1;i<=n+1;i++)
        for(int j=0;j<state.size();j++)
            if(!(state[j] & g[i]))
                for(int k : head[j])
                    f[i][j] = (f[i][j] + f[i - 1][k]) % mod;

    cout << f[n + 1][0] << endl;

    return 0;
}


活动打卡代码 AcWing 1064. 小国王

奇点lzy
1个月前
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << 10, K = 110;

int n,m;
vector<int> state;
int cnt[M];
vector<int> head[M];
LL f[N][K][M];

bool check(int state)
{
    for(int i=0;i<n;i++)
        if((state >> i & 1) && (state >> i + 1 & 1))
            return false;
    return true;        
}

int count(int state)
{
    int res = 0;
    for(int i=0;i<n;i++) res += state >> i & 1;
    return res;
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<1<<n;i++)
        if(check(i))
        {
            state.push_back(i);
            cnt[i] = count(i);
        }

    for(int i=0;i<state.size();i++)
        for(int j=0;j<state.size();j++)
        {
            int a = state[i], b = state[j];
            if((a & b) == 0 && check(a | b))
                head[i].push_back(j);
        }

    f[0][0][0] = 1;

    for(int i=1;i<=n+1;i++)
        for(int j=0;j<=m;j++)
            for(int a=0;a<state.size();a++)
                for(int b : head[a])
                {
                    int c = cnt[state[a]];
                    if(c<=j)
                        f[i][j][a] += f[i - 1][j - c][b];
                }

    cout << f[n + 1][m][0] << endl;            

    return 0;
}