头像

smallfang

害怕的人


访客:1789

离线:1天前



smallfang
27天前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 800, M = 800, INF = 1e9;

int n, m, k;
int f[N][M];

int main()
{
    ios::sync_with_stdio(false);
    cin >> k >> n >> m;
    int res = 0;
    while (k -- )
    {
        int x, y, w;
        cin >> x >> y >> w;
        for (int i = n; i >= x; i -- )
        {
            for (int j = m; j >= y; j -- )
            {
                f[i][j] = max(f[i][j], f[i - x][j - y] + w);
            }
        }
    }
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            res = max(res, f[i][j]);
        }
    }
    cout << res;
    return 0;
}



smallfang
28天前
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e3 + 5, M = 5e3 + 5;

int f[N][M];

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i ++ )
    {
        int v, w;
        cin >> v >> w;
        for (int j = n; j >= v; j -- )
        {
            for (int k = m - 1; k >= w; k -- )
            {
                f[j][k] = max(f[j][k], f[j - v][k - w] + 1);
            }
        }

    }
    int res = 0;
    cout << f[n][m - 1] << " ";
    k = m - 1;
    while (k > 0 && f[n][k - 1] == f[n][m - 1]) k -- ;
    cout << m - k;
    return 0;
}


活动打卡代码 AcWing 275. 传纸条

smallfang
29天前

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

int m, n;
int g[51][51];
int f[101][51][51];

int main()
{
scanf(“%d%d”, &m, &n);
for(int i = 1; i <= m; i )
{
for(int j = 1; j <= n; j
)
{
scanf(“%d”, &g[i][j]);
}
}
for(int k = 2; k <= m + n; k)
{
for(int i1 = max(1, k - n); i1 <= min(k - 1, m); i1
)
{
for(int i2 = max(1, k - n); i2 <= min(k - 1, m); i2 ++)
{
int j1 = k - i1, j2 = k - i2;
int res = g[i1][j1];
if(i1 != i2)
{
res += g[i2][j2];
}
int &tmp = f[k][i1][i2];
tmp = max(tmp, f[k - 1][i1 - 1][i2 - 1] + res);
tmp = max(tmp, f[k - 1][i1 - 1][i2] + res);
tmp = max(tmp, f[k - 1][i1][i2 - 1] + res);
tmp = max(tmp, f[k - 1][i1][i2] + res);
}
}
}
printf(“%d”,f[n + m][m][m]);
return 0;
}



活动打卡代码 AcWing 1024. 装箱问题

smallfang
29天前
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5 + 5;

int f[N];

int main()
{
    int k, n;
    scanf("%d%d", &k, &n);
    for (int i = 1; i <= n; i ++ )
    {
        int v;
        scanf("%d", &v);
        for (int j = k; j >= v; j --)
            f[j] = max(f[j], f[j - v] + v);
    }
    printf("%d", k - f[k]);
    return 0;
}


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

smallfang
1个月前
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int N = 1e2 + 5, M = 12, K = (1 << 10) + 5;

int f[2][K][K], g[N], cnt[K];
vector<int> status, head[N];
int n, m;

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

int cnts(int x)
{
    int cntf = 0;
    for (int i = 0; i < m; i ++ )
    {
        cntf += x >> i & 1;
    }
    return cntf;
}

int main()
{  
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
       for (int j = 0; j < m; j ++ )
       {
            char x;
            cin >> x;
            g[i] += (x == 'H') * (1 << j);
       }
    }
    int lena = 1 << m;
    for (int i = 0; i < lena; i ++ )
    {
        if(check(i))
        {
            status.push_back(i);
            cnt[i] = cnts(i);
        }
    }
    int len = status.size();
    for (int i = 1; i <= n + 2; i ++ )
    {
        for (int a = 0; a < len; a ++ )
        {
            for (int b = 0; b < len; b ++ )
            {
                for (int c = 0; c < len; c ++ )
                {
                    int x = status[a], y = status[b], z = status[c];
                    if ((x & y) | (y & z) | (x & z))
                    {
                        continue;
                    }
                    if ((g[i - 1] & x) | (g[i] & y))
                    {
                        continue;
                    }
                    f[i & 1][a][b] = max(f[i & 1][a][b], f[(i - 1) & 1][c][a] + cnt[y]);
                }
            }
        }
    }
    printf("%d", f[(n + 2) & 1][0][0]);
}


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

smallfang
1个月前

#include <iostream>
#include <vector>

using namespace std;

const int N = 15, K = (1 << 12) + 5, mod = 1e8;

int f[N][K], m, n, g[N];
vector<int> status, head[N];

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

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int x;
            scanf("%d", &x);
            g[i] += !x << j;
        }
    }
    int lena = 1 << m;
    for (int i = 0; i < lena; i ++ )
    {
        if (check(i))
        {
            status.push_back(i);
        }
    }
    int len = status.size();
    for (int i = 0; i < len; i ++ )
    {
        for (int j = 0; j < len; j ++ )
        {
            int a = status[i];
            int b = status[j];
            if ((a & b) == 0)
            {
                head[i].push_back(j);
            }
        }
    }
    f[0][0] = 1;
    for (int i = 1; i <= n + 1; i ++ )
    {
        for (int j = 0; j < len; j ++ )
        {
            int lens = head[j].size();
            for (int k = 0; k < lens; k ++ )
            {
                int a = status[j], b = head[j][k];
                if (g[i] & a)
                {
                    continue;
                }
                f[i][j] = (f[i][j] + f[i - 1][b]) % mod;
            }
        }
    }
    printf("%d", f[n + 1][0] % mod);    
}


活动打卡代码 AcWing 423. 采药

smallfang
1个月前
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e3 + 5;

int n, V, v, w, f[N];

int main()
{
    scanf("%d%d", &V, &n);
    for (int i = 1; i <= n; i ++ )
    {
        int v, w;
        scanf("%d%d", &v, &w);
        for (int j = V; j >= v; j -- )
        {
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    printf("%d", f[V]);
    return 0;
}


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

smallfang
1个月前
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>

using namespace std;

const int  N = 15, M = (1 << 10) + 15, K = 100 + 15;  

typedef long long LL;

vector<int> status;
vector<int> h[M];
LL f[N][K][M];
int n, k, cnt[M];

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

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


int main()
{
    scanf("%d%d", &n, &k);
    int lenn = 1 << n;
    for (int i = 0; i < lenn; i ++ )
    {
        if (check(i))
        {
            status.push_back(i);
            cnt[i] = cnts(i);
        }
    }
    int len = status.size();
    for (int i = 0; i < len; i ++ )
    {
        for (int j = 0; j < len; j ++ )
        {
            int a = status[i], b = status[j];
            if ((a & b) == 0 && (check(a | b)))
            {
                h[i].push_back(j);
            }
        }
    }
    f[0][0][0] = 1;
    for (int i = 1; i <= n + 1; i ++ )
    {
        for (int j = 0; j <= k; j ++ )
        {
            for (int a = 0; a < len; a ++ )
            {
                int len2 = h[a].size();
                for (int b = 0; b < len2; b ++ )
                {
                    int ne = h[a][b];
                    int c = cnt[status[a]];
                    if (j >= c)
                    {
                        f[i][j][a] += f[i - 1][j - c][ne];
                    }
                }
            }
        }
    }
    printf("%lld", f[n + 1][k][0]);
    return 0;
}


活动打卡代码 AcWing 1052. 设计密码

smallfang
1个月前
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 50 + 5, mod = 1e9 + 7;

int f[N][N], nxt[N], n;
char str[N];

int main()
{
    cin >> n >> str + 1;
    int m = strlen(str + 1);
    int j = 0;
    for (int i = 2; i <= n; i ++ )
    {
        while (j && str[i] != str[j + 1])
            j = nxt[j];
        if (str[i] == str[j + 1])
            j ++;
        nxt[i] = j;
    }
    f[0][0] = 1;
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            for (char k = 'a'; k <= 'z'; k ++ )
            {
                int u = j;
                while (u && str[u + 1] != k)
                    u = nxt[u];
                if (str[u + 1] == k)
                    u ++;
                if (u < m)
                    f[i + 1][u] = (f[i + 1][u] + f[i][j]) % mod; 
            }
        }
    }
    int res = 0;
    for (int i = 0; i < m; i ++ )
    {
        res = (res + f[n][i]) % mod;
    }
    printf("%d", res);
    return 0;
}


活动打卡代码 AcWing 1058. 股票买卖 V

smallfang
1个月前
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5 + 5, INF = 2e9;

int a[N], f[N][3], n;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
    }
    f[0][0] = -INF;
    f[0][1] = -INF;
    for (int i = 1; i <= n; i ++ )
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][2] - a[i]);
        f[i][1] = f[i - 1][0] + a[i];
        f[i][2] = max(f[i - 1][1], f[i - 1][2]);
    }
    printf("%d", max(f[n][0], max(f[n][1], f[n][2])));
    return 0;
}