头像

kurocardo

宁夏理工学院




离线:1天前


活动打卡代码 AcWing 1057. 股票买卖 IV

/*
  Problem Name:股票买卖Ⅳ
  algorithm tag:状态机dp
*/

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;

const int N = 1e5 + 5;

int dp[105][2];
int w[N];
int n, k;

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

    for (int i = 1; i <= n;i++)
        cin >> w[i];
    memset(dp, 0xcf, sizeof dp);
    dp[0][0] = 0;
    for (int i = 1; i <= n;i++){
        for (int j = k; j >= 1;j--){
            dp[j][0] = dp[j][0];
            dp[j][0] = max(dp[j][0], dp[j][1] + w[i]);
            dp[j][1] = dp[j][1];
            dp[j][1] = max(dp[j][1], dp[j - 1][0] - w[i]);
        }
    }
    int res = 0;
    for (int i = 0; i <= k;i++){
        res = max(res, dp[i][0]);
    }

    cout << res << endl;
}



活动打卡代码 AcWing 1049. 大盗阿福

/*
  Problem Name:大盗阿福
  algorithm tag:状态机,线性dp
*/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
typedef pair<int,int> pii;

const int N = 1e5 + 5;
int a[N];
int dp[N][2];

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

    while(t--){
        int n;
        cin >> n;

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

        for (int i = 1; i <= n;i++){
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][0] + a[i];
        }

        cout << max(dp[n][0], dp[n][1]) << endl;
    }
}



/*
  Problem Name:金明的预算方案
  algorithm tag:有依赖的背包,分组背包,01背包,泛化背包
*/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int,int> pii;

const int M = 32005;
int n, m;
int dp[65][M];
vector<int> v[65], w[65];


int main()
{
    cin >> m >> n;
    int idx = 0;
    int cnt = 0;
    for (int i = 1; i <= n;i++){
        int x, y, z;
        cin >> x >> y >> z;

        if(z==0){
            v[i].push_back(x);
            w[i].push_back(y*x);
        }
        else{
            if(v[z].size()==1){
                v[z].push_back(x+v[z][0]);
                w[z].push_back(y*x+w[z][0]);
            }
            else if(v[z].size()==2){
                v[z].push_back(x + v[z][0]);
                w[z].push_back(y*x + w[z][0]);
                v[z].push_back(x + v[z][1]);
                w[z].push_back(y*x + w[z][1]);
            }
        }
    }
    for (int i = 1; i <= n;i++){
        for (int j = 0; j <= m;j++){
            dp[i][j] = dp[i - 1][j];
            for (int k = 0; k < v[i].size();k++){
                if(j>=v[i][k])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i][k]] + w[i][k]);
            }
        }
    }

    cout << dp[n][m] << endl;
}


活动打卡代码 AcWing 734. 能量石

/*
  Problem Name:能量石
  algorithm tag:背包,贪心
*/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int,int> pii;
int t;
int f[10005];

struct Stone
{
    int s, e, l;
    bool operator<(const Stone &x) const
    {
        return s * x.l < x.s * l;
    }
} stone[105];

int main()
{
    cin >> t;
    int idx = 0;

    while (t--) {
        int n;
        cin >> n;
        int m = 0;
        memset(f, 0xcf, sizeof f);
        f[0] = 0;
        for (int i = 1; i <= n; i++) {
            int s, e, l;
            cin >> s >> e >> l;
            stone[i] = {s, e, l};
            m += s;
        }

        //贪心缩小枚举范围
        sort(stone + 1, stone + 1 + n);
        //为什么使用"恰好j"而不是"不超过j"
        //我的理解是这样的:首先"恰好j"加上遍历体积也是可以算出"不超过j"的最大值的
        //事实上"不超过j"的是包含f[0~m]的最值,
        //而我们取max的f[j-s]+"e-(j-s)*l"<-这里的j是确定的。
        //所以得出来的结果会是有错的。
        for (int i = 1; i <= n; i++) {
            int s = stone[i].s;
            int e = stone[i].e;
            int l = stone[i].l;
            for (int j = m; j >= s; j--) {
                f[j] = max(f[j], max(f[j - s] + e - (j - s) * l, 0));
            }
        }

        int res = 0;
        for (int i = 1; i <= m; i++)
            res = max(res, f[i]);

        printf("Case #%d: %d\n", ++idx, res);
    }
}



//背包问题求具体方案
//tag:背包九讲

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int, int> pii;

const int N = 1005;

int n, m;
int dp[N][N];
int g[N][N];
int w[N], v[N];

void solve1()
{
    cin >> n >> m;

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

    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = dp[i + 1][j];
            if (j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i + 1][j - v[i]] + w[i]);
        }
    }

    int j = m;

    for (int i = 1; i <= n; i++)
        if (j >= v[i] && dp[i][j] == dp[i + 1][j - v[i]] + w[i]) {
            cout << i << " ";
            j -= v[i];
        }
}

void solve2()//非字典序求具体方案g数组求法
{
    cin >> n >> m;

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

    for (int i = 1; i <= n;i++){
        for (int j = 0; j <= m;j++){
            int maxv = dp[i - 1][j];
            if(j>=v[i])
                maxv = max(maxv, dp[i - 1][j - v[i]] + w[i]);
            if(maxv==dp[i-1][j])
                g[i][j] = 0;
            else if(maxv==dp[i-1][j-v[i]]+w[i])
                g[i][j] = 1;
        }
    }

    cout << dp[n][m] << endl;

    int j = m;

    for (int i = n; i >= 1;i--){
        if (j >= v[i] && g[i][j] == 1){
            cout << i << " ";
            j -= v[i];
        }
    }
}

int main()
{
    solve1();
}




IMG_0182.PNG

//贪心
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int, int> pii;

int t;
int n, x;
int a[505];
int b[505];

int main()
{
    cin >> t;

    while (t--) {
        cin >> n >> x;

        for (int i = 1; i <= n; i++)
            cin >> a[i], b[i] = a[i];

        sort(a + 1, a + n + 1);
        bool flag = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] != b[i]) {
                flag = 1;
                break;
            }
        }
        int tmp = x;
        int pos = 0;
        for (int i = n; i >= 2; i--) {
            if (b[i] < b[i - 1]) {
                pos = i - 1;
                break;
            }
        }
        if (!flag) {
            cout << 0 << endl;
            continue;
        }
        int cnt = 0;
        //cout << pos << " ";
        for (int i = 1; i <= n; i++) {
            if (x < b[i] && i <= pos) {
                swap(x, b[i]);
                cnt++;
            }
            if (i > pos && b[i + 1] < b[i] && i < n) {
                swap(x, b[i]);
                cnt++;
            }
            a[i] = b[i];
        }
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; i++) {
            if (a[i] != b[i]) {
                flag = 0;
                break;
            }
        }

        if (flag)
            cout << cnt << endl;
        else
            cout << -1 << endl;
    }
}




//背包问题求方案数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9+7;
typedef pair<int,int> pii;

const int N = 1005;

int n, m;
int w[N], v[N];
int dp[N];
ll dp2[N];

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

    memset(dp, -0x3f, sizeof dp);
    dp[0] = 0;
    dp2[0] = 1;

    for (int i = 1; i <= n;i++)
        cin >> v[i] >> w[i];
    //先采用恰好为m的方法求出方案数
    for (int i = 1; i <= n;i++){
        for (int j = m; j >= v[i];j--){
            int maxv = max(dp[j], dp[j - v[i]] + w[i]);
            int s = 0;
            if(maxv==dp[j])
                s += dp2[j] % mod;
            if(maxv==dp[j-v[i]]+w[i])
                s += dp2[j - v[i]] % mod;
            dp[j] = maxv, dp2[j] = s % mod;
        }
    }
    int res = 0;
    //求出最大
    for (int i = 0; i <= m;i++)
        res = max(res, dp[i]);
    ll ans = 0;
    //求出方案数
    for (int i = 0; i <= m;i++)
        if(res==dp[i])
            ans = (ans + dp2[i]) % mod;

    cout << ans << endl;
}



IMG_0181.PNG

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int,int> pii;

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

    while(t--){
        int x, y;
        cin >> x >> y;
        cout << x - 1 << " " << y << endl;
    }
}



IMG_0180.PNG

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int, int> pii;

const int N = 1e6;
int t;

int main()
{
    cin >> t;

    while (t--) {
        int n;

        cin >> n;
        int ans = 0;
        for (int i = 1; i <= n;i++){
            int sum = i * (i + 1) / 2;
            if(sum>=n){
                sum = sum - n;
                if(sum==0||sum>=2){
                    ans = i;
                    break;
                }
                else{
                    ans = i + 1;
                    break;
                }
            }
            else
                continue;
        }

        cout<<ans<<endl;
    }
}



//有依赖的背包
//泛化背包

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int,int> pii;

const int N = 104;

int n, m;
int v[N], w[N];
int h[N], e[N], ne[N], idx;
int dp[N][N];

void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u)
{
    for (int i = h[u]; ~i;i=ne[i]){

        int son = e[i];

        dfs(son);

        for (int j = m - v[u]; j >= 0;j--)
            for (int k = 0; k <= j;k++)
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]);
    }
    for (int i = m; i >= v[u];i--)
        dp[u][i] = dp[u][i - v[u]] + w[u];
    for (int i = 0; i < v[u];i++)
        dp[u][i] = 0;
}

int main()
{
    cin >> n >> m;
    int root = 0;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n;i++){
        int p;
        cin >> v[i] >> w[i] >> p;
        if(p==-1)
            root = i;
        else
            add(p, i);
    }
    dfs(root);

    cout << dp[root][m] << endl;
}