头像

youwike




离线:22小时前



youwike
17天前

rt




youwike
6个月前
#define ll long long
class Solution {
public:
    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        int mod = 1e9 + 7;
        int maxh = INT_MIN;
        horizontalCuts.push_back(h);
        sort(horizontalCuts.begin(), horizontalCuts.end());
        for (int i = 1; i < horizontalCuts.size(); ++ i)
        {
            maxh = max(maxh, horizontalCuts[i] - horizontalCuts[i - 1]);
        }
        maxh = max(maxh, horizontalCuts[0]);
        int maxw = INT_MIN;
        verticalCuts.push_back(w);
        sort(verticalCuts.begin(), verticalCuts.end());
        for (int i = 1; i < verticalCuts.size(); ++ i)
        {
            maxw = max(maxw, verticalCuts[i] - verticalCuts[i - 1]);
        }
        maxw = max(maxw, verticalCuts[0]);
        return (long long)maxh * maxw % 1000000007;
    }
};



youwike
6个月前
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = INT_MIN;
        for (int i = 0; i < nums.size(); ++ i)
        {
            for (int j = i + 1; j < nums.size(); ++ j)
            {
                res = max(res, (nums[i] - 1) * (nums[j] - 1));
            }
        }
        return res;
    }
};


活动打卡代码 AcWing 289. 环路运输

youwike
7个月前
#include <iostream>
#include <cstdio>
#include <deque>

using namespace std;

const int N = 3e6 + 10;
deque<pair<int, int> > que;
int a[N], n, m;

inline int read()
{
    int res = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        res = (res << 3) +(res << 1) + c - 48;
        c = getchar();
    }
    return res * f;
}

int main()
{
    n = read();
    for (int i = 1; i <= n; ++ i)
    {
        a[i] = read();
        a[i + n] = a[i];
    }
    m = n;
    n = n * 2;
    int ans = -1 << 30;
    que.push_back(make_pair(a[1] - 1, 1));
    for (int i = 2; i <= n; ++ i)
    {
        int now = i, data = a[i] - i;
        if (que.size() && que.front().second < now - m / 2) que.pop_front();
        ans = max(ans, que.front().first + a[i] + i);
        while (que.size() && que.back().first < data) que.pop_back();
        que.push_back(make_pair(data, now));
    }
    cout << ans;
    return 0;
}


活动打卡代码 AcWing 288. 休息时间

youwike
7个月前
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 4000;
int f[2][N][2], n, B, v[N], ans;

int main()
{
    scanf("%d%d", &n, &B);
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%d", &v[i]);
    }
    memset(f, -0x3f, sizeof(f));
    f[1][0][0] = 0;
    f[1][1][1] = 0;
    for (int i = 2; i <= n; ++ i)
    {
        for (int j = 0; j <= B; ++ j)
        {
            f[i & 1][j][0] = max(f[i - 1 & 1][j][1], f[i - 1 & 1][j][0]);
            if (j > 0)
                f[i & 1][j][1] = max(f[i - 1 & 1][j - 1][0], f[i - 1 & 1][j - 1][1] + v[i]);
        }
    }
    ans = max(f[n & 1][B][0], f[n & 1][B][1]);
    memset(f, -0x3f, sizeof(f));
    f[1][1][1] = v[1];
    for (int i = 2; i <= n; ++ i)
    {
        for (int j = 0; j <= B; ++ j)
        {
            f[i & 1][j][0] = max(f[i - 1 & 1][j][1], f[i - 1 & 1][j][0]);
            if (j > 0)
                f[i & 1][j][1] = max(f[i - 1 & 1][j - 1][0], f[i - 1 & 1][j - 1][1] + v[i]);
        }
    }
    ans = max(ans, f[n & 1][B][1]);
    cout << ans;
    return 0;
}


活动打卡代码 AcWing 286. 选课

youwike
7个月前
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 330, M = 330;
int to[N], f[N][M], nxt[N], king, head[N], k[N], n, m, v[N], fa[N];
int cnt;

void add(int x, int y)
{
    to[++ cnt] = y;
    nxt[cnt] = head[x];
    head[x] = cnt;
}

void dfs(int now)
{
    for (int i = head[now]; i; i = nxt[i])
    {
        int ver = to[i];
        dfs(ver);
        for (int j = m - 1; j; -- j)
        {
            for (int k = 1; k <= j; ++ k)
            {
                f[now][j] = max(f[now][j], f[ver][k] + f[now][j - k]);
            }
        }
    }
    for (int i = m; i; -- i) f[now][i] = f[now][i - 1] + v[now];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%d%d", &fa[i], &v[i]);
        add(fa[i], i);
    }
    ++ m;
    dfs(0);
    cout << f[0][m];
    return 0;
}



youwike
7个月前
#include<iostream>
#include<vector>
#include<cstdio>
#define Vto(i,x) for(vector<int>::iterator i=x.begin();i!=x.end();i++)

using namespace std;

const int N=6060;
vector<int> map[N];
int f[N][2],king[N],nu[N];
int n,v[N],k,l,s;
int ans;

int dfs(int now)
{
    int dp=0;
    if(!nu[now])
    {
        return v[now];
    }
    Vto(i,map[now])
    {
        dp+=dfs(*i);
    }
    f[now][0]=dp;
    ans=max(f[now][0],ans);
    dp=0;
    Vto(i,map[now])
    {
        dp+=f[*i][0];
    }
    f[now][1]=dp+v[now];
    ans=max(f[now][1],ans);
    return max(f[now][1],f[now][0]);
}

int main()
{
    int n;
    cin>>n;
    if (n == 1)
    {
        cout << 1;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for(int i=1;i<n;i++)
    {
        cin>>l>>k;
        king[l]=1;
        nu[k]=1;
        map[k].push_back(l);
    }
    for(int i=1;i<=n;i++)
    {
        if(!king[i]) s=i;
    }
    dfs(s);
    cout<<ans;
    return 0;
}


活动打卡代码 AcWing 284. 金字塔

youwike
7个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long 

using namespace std;

const int mod = 1e9, N = 400;
ll f[N][N];
char s[N];

int main()
{
    cin >> s + 1;
    int n = strlen(s + 1);
    for (int i = 1; i <= n; ++ i)
    {
        f[i][i] = 1;
    }
    for (int  len = 1; len <= n; len += 2)
    {
        for (int l = 1; l <= (n - len + 1); ++ l)
        {
            int r = (l + len - 1);
            for (int mid = l; mid < r; mid += 2)
            {
                if (s[mid] == s[r])
                f[l][r] = (f[l][r] + f[l][mid] * f[mid + 1][r - 1]) % mod;
            }
        }
    }
    cout << f[1][n];
    return 0;
}


活动打卡代码 AcWing 283. 多边形

youwike
7个月前
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 60;
int maxx[4 * N][4 * N], n, minn[4 * N][4 * N];
char c[4 * N];

int main()
{
    cin >> n;
    memset(minn,0x3f3f,sizeof(minn));
    memset(maxx,128,sizeof(maxx));
    for (int i = 1; i <= n * 2; ++ i)
    {
        if (i & 1)
        {
            cin >> c[i / 2 + 1];
            c[i / 2 + 1 + n] = c[i / 2 + 1];
        }
        else
        {
            cin >> minn[i / 2][i / 2];
            maxx[i / 2][i / 2] = minn[i / 2][i / 2];
            minn[i / 2 + n][i / 2 + n] = minn[i / 2][i / 2];
            maxx[i / 2 + n][i / 2 + n] = maxx[i / 2][i / 2];
        }
    }
    int m = n;
    n = n * 2;
    for (int len = 2; len <= m; ++ len)
    {
        for (int l = 1; l <= (n - len + 1); ++ l)
        {
            int r = (l + len - 1);
            for (int mid = l; mid < r; ++ mid)
            {
                if (c[mid + 1] == 't')
                {
                    minn[l][r] = min(minn[l][r], minn[l][mid] + minn[mid + 1][r]);
                    maxx[l][r] = max(maxx[l][r], maxx[l][mid] + maxx[mid + 1][r]);
                }
                else
                {
                    minn[l][r] = min(minn[l][r], minn[l][mid] * minn[mid + 1][r]);
                    minn[l][r] = min(minn[l][r], minn[l][mid] * maxx[mid + 1][r]);
                    minn[l][r] = min(minn[l][r], maxx[l][mid] * minn[mid + 1][r]);
                    maxx[l][r] = max(maxx[l][r], maxx[l][mid] * maxx[mid + 1][r]);
                    maxx[l][r] = max(maxx[l][r], minn[l][mid] * minn[mid + 1][r]);
                }
            }
        }
    }
    int ans1 = -1e9 - 7;
    for (int i = 1; i <= m; ++ i)
    {
        ans1 = max(ans1, maxx[i][i + m - 1]);
    }
    cout << ans1 << endl;
    for (int i = 1; i <= m; ++ i)
    {
        if (ans1 == maxx[i][i + m - 1])
        {
            cout << i << ' ';
        }
    }
    return 0;
}


活动打卡代码 AcWing 282. 石子合并

youwike
7个月前
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 333;
int f[N][N], s[N], n;

inline int read()
{
    int res = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        res = (res << 3) + (res << 1) + c - 48;
        c = getchar();
    }
    return res * f;
}

int main()
{
    n = read();
    fill(f[0], f[n] + n, 1e9 + 7);
    for (int i = 1; i <= n; ++ i)
    {
        s[i] = read();
        f[i][i] = 0;
    }
    for (int i = 1; i <= n; ++ i)
    {
        s[i] += s[i - 1];
    }
    for (int len = 2; len <= n; ++ len)
    {
        for (int l = 1; l <= (n - len + 1); ++ l)
        {
            int r = (l + len - 1);
            for (int mid = l; mid < r; ++ mid)
            {
                f[l][r] = min(f[l][r], f[l][mid] + f[mid + 1][r] + s[r] - s[l - 1]);
            }
        }
    }
    cout << f[1][n];
    return 0;
}