头像

dellqang




离线:1个月前



dellqang
9个月前
#include<iostream>

using namespace std;

const int N = 1e5+10, K = 110, INF = -0x3f3f3f3f;
int f[N][K][2];
int w[N];

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

    //对f进行初始化
    f[0][0][0] = 0;
    for(int i=0; i<=k; i++) f[0][i][1] = INF;

    for(int i=1; i<=n; i++)
        for(int j=1; j<=k; j++)
        {
            f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1]+w[i]);
            f[i][j][1] = max(f[i-1][j][1], f[i-1][j-1][0]-w[i]);
        }

    int res = 0;
   // for(int i=1; i<=k; i++) res = max(res, f[n][i][0]); //不一定第k次交易后最大;
    cout << f[n][k][0] << endl; // 因为f[0][j][0]=0, 因此肯定f[n][k][0]最大

    return 0;
}



活动打卡代码 AcWing 7. 混合背包问题

dellqang
9个月前
#include<iostream>

using namespace std;

const int N = 1010;
int f[N];

int main(){
    int n, v; cin >> n >> v;
    for(int i=0; i<n; i++){
        int vi, wi, si; cin >> vi >> wi >> si;
        if(!si){
            for(int j=vi; j<=v; j++) f[j] = max(f[j], f[j-vi]+wi);
        }else{
            if(si==-1) si=1; // 零一背包问题是特殊的多重背包问题
            int k = 1;
            while(si>=k){
                for(int j=v; j>=vi*k; j--){
                    f[j] = max(f[j], f[j-vi*k]+wi*k);
                }
                si -= k; //这一步用于确保 1,2,2*2,...,2^k,res 的和为si,👍
                k*=2;
            }
            if(si>0){
                for(int j=v; j>=vi*si; j--){
                    f[j] = max(f[j], f[j-vi*si]+wi*si);
                }
            }
        }
    }
    cout << f[v] << endl;
    return 0;
}


活动打卡代码 AcWing 7. 混合背包问题

dellqang
9个月前
#include<iostream>

using namespace std;

const int N = 1010;
int f[N];

int main(){
    int n, v; cin >> n >> v;
    for(int i=0; i<n; i++){
        int vi, wi, si; cin >> vi >> wi >> si;
        if(!si){
            for(int j=vi; j<=v; j++) f[j] = max(f[j], f[j-vi]+wi);
        }else{
            if(si==-1) si=1; // 零一背包问题是特殊的多重背包问题
            int k = 1;
            while(si>=k){
                for(int j=v; j>=vi*k; j--){
                    f[j] = max(f[j], f[j-vi*k]+wi*k);
                }
                si -= k; //这一步用于确保 1,2,2*2,...,2^k,res 的和为si,👍
                k*=2;
            }
            if(si>0){
                for(int j=v; j>=vi*si; j--){
                    f[j] = max(f[j], f[j-vi*si]+wi*si);
                }
            }
        }
    }
    cout << f[v] << endl;
    return 0;
}


活动打卡代码 AcWing 532. 货币系统

dellqang
9个月前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 110, M=25010;
int a[N], f[M];

int main(){
    int T; cin >> T;
    while(T--){
        int n; cin >> n;
        for(int i=0; i<n; i++){
            cin >> a[i];
        }
        sort(a, a+n);

        int m = a[n-1];    //可以缩小数据表示范围,good👍
        memset(f,0,sizeof f); f[0] = 1; //每次均要对f重新初始化  

        int res = 0;
        for(int i=0; i<n; i++){
            if(!f[a[i]]) res++;    // 不可表示数直接加一,而可表示数对f没有任何影响。
            for(int j=a[i];j<=m; j++){
                f[j] = f[j] + f[j-a[i]];
            }
        }
        cout << res << endl;
    }
    return 0;
}




dellqang
9个月前
#include<iostream>

using namespace std;

const int N = 110;
int f[N];


int main(){
    int n, m; cin >> n >> m;
    f[0] = 1; // 这一步开始没想明白
    for(int i=0; i<n; i++){
        int a; cin >> a;
        for(int j=m;j>=a;j--){
            f[j]  = f[j] + f[j-a];
        }
    }
    cout << f[m] << endl;
    return 0;
}



dellqang
9个月前

错误代码

#include<iostream>
#include<cstring>
using namespace std;

// f[i][j] 要达到f[i][j]至少要花费的体积

int f[30][100];

int main(){
    int m, n, k; cin >> m>>n>>k;
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    while(k--){
        int a, b, c; cin >> a >> b >> c;
        for(int i=m; i>0; i--){
            for(int j=n;j>0; j--){
                if(a>=i&&b>=j) f[i][j] = min(f[i][j], c);
                if(i>=a&&j>=b) f[i][j] = min(f[i-a][j-b]+c, f[i][j]);
            }
        }
    }
    cout << f[m][n] << endl;
    return 0;

}

正确代码

#include<iostream>
#include<cstring>
using namespace std;

// f[i][j] 要达到f[i][j]至少要花费的体积

int f[30][100];

int main(){
    int m, n, k; cin >> m>>n>>k;
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    while(k--){
        int a, b, c; cin >> a >> b >> c;
        for(int i=m; i>=0; i--){
            for(int j=n;j>=0; j--){
                f[i][j] = min(f[i][j], f[max(0, i - a)][max(0, j-b)] +c);
            }
        }
    }
    cout << f[m][n] << endl;
    return 0;

}

错误原因

没有考虑罐某一项为零的情况




dellqang
9个月前
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 60;
int a[N];
int up[N], down[N];
int ans;
int n;

// su表示当前上升导弹的数目, 同理sd
void dfs(int t, int su, int sd){
    if(su+sd >= ans) return; // 这一步剪枝,提前减掉不好的分枝  >= 相比 > 时间复杂度更低
    if(t==n) {
        ans = su + sd; // 由于上一步剪枝,因此ans为当前方案数的最小值
        return;
    }

    // 将当前导弹加入上升序列中
    int k = 0;
    while(k<su&&a[t]<=up[k]) k++;
    int status = up[k];
    up[k] = a[t];
    if(k>=su) dfs(t+1, su+1, sd);
    else dfs(t+1, su, sd);  // 当时把这一步搞丢了
    up[k] = status;

    // 将当前导弹加入下降序列中
    k=0;
    while(k<sd&&a[t]>=down[k]) k++;
    status = down[k];
    down[k] = a[t];
    if(k>=sd) dfs(t+1,su, sd+1);
    else dfs(t+1, su, sd);
    down[k] = status;
}


int main(){
    while(cin>>n, n){
    for(int i=0; i<n; i++) cin >> a[i];
    ans = n;
    dfs(0,0,0);
    cout << ans << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1010. 拦截导弹

dellqang
9个月前
#include<iostream>
#include<algorithm>

using namespace std;

const int N=1010;
int a[N];
int f[N], g[N];

int main(){
    int n=0;
    while(cin>>a[n]) n++;

    int res = 0;
    for(int i=0; i<n; i++){
        f[i] = 1;
        for(int j=0; j<i; j++){
            if(a[i]<=a[j]){
                f[i] = max(f[i], f[j]+1);
            }
        }
        res = max(res, f[i]);
    }
    cout << res << endl;

    int cnt = 0;
    for(int i=0; i<n; i++){
        int k=0;
        while(k<cnt&&a[i]>g[k]) k++;
        g[k] = a[i];
        if(k>=cnt) cnt++;
    }
    cout << cnt << endl;
}



dellqang
9个月前

开始想的是每个数字占据一个空间,然后计算。这样实在太低效了,应该只计算出现过的数字就可以了。
后来还想用不用先来一个set将他们映射为连续的数值空间,后来发现完全没必要

#include<iostream>

using namespace std;

const int N = 1010;
int w[N], dp[N];

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

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

    int res = 0;
    for(int i=0; i<n; i++) res = max(res, dp[i]);
    cout << res;

    return 0;
}



dellqang
9个月前

// 这个是换位思考,f[i]表示长度为i的子序列最少于那个数结尾。
#include<iostream>

using namespace std;

const int N = 1e5+10;
int w[N], f[N];

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

    f[0] = -1e9; // 这一步很赞
    len = 0;
    for(int i=0; i<n; i++){
        int l = 0, r = len;
        while(l!=r){
            int mid = l + r +1 >> 1;
            if(f[mid]>w[i]){
                r = mid-1;
            }else{
                l = mid;
            }
        }
        len = max(len, r+1);
        f[r+1] = w[i];
    }
    cout << len;
    return 0;
}