526互联

7/22·morning

发布时间 2023-07-22 11:06:34作者: 臧清宇

1269：【例9.13】庆功会  http://ybt.ssoier.cn:8088/problem_show.php?pid=1269

#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[503],v[503],s[503];
int dp[6007];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i]>>s[i];
    }
    for(int i=1;i<=n;i++){
        for(int k=1;k<=s[i];k++){
            for(int j=m;j>=0;j--){
                if(j-w[i]>=0&&dp[j-w[i]]+v[i]>dp[j]){
                    dp[j]=dp[j-w[i]]+v[i];
                }
            }
        }
    }
    cout<<dp[m];
    return 0;
}

 

1270：【例9.14】混合背包  http://ybt.ssoier.cn:8088/problem_show.php?pid=1270

#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[31],v[31],s[31];
int dp[203];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i]>>s[i];
        if(s[i]==0)s[i]=m/w[i]+5;
    }
    for(int i=1;i<=n;i++){
        for(int k=1;k<=s[i];k++){
            for(int j=m;j>=0;j--){
                if(j-w[i]>=0&&dp[j-w[i]]+v[i]>dp[j]){
                    dp[j]=dp[j-w[i]]+v[i];
                }
            }
        }
    }
    cout<<dp[m];
    return 0;
}

 

1258：【例9.2】数字金字  http://ybt.ssoier.cn:8088/problem_show.php?pid=1258

枚举10% 记忆化+递归100% dp100%

#include<bits/stdc++.h>
using namespace std;
long long R;
long long a[1003][1005];
int main(){
    cin>>R;
    for(long long i=1;i<=R;i++){
        for(long long j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    long long maxx=0;
    for(long long i=0;i<pow(2,R-1);i++){
        long long n=i;
        long long s=a[1][1],x=1;
        for(long long j=2;j<=R;j++){
            if(n%2==1)x++;
            n=n/2;
            s+=a[j][x];
        }
        maxx=max(maxx,s);
    }
    cout<<maxx;
    return 0;
}
/*
10%枚举
未通过 10分
测试点1: 答案正确 628KB 4MS
测试点2: 答案错误 768KB 9MS
测试点3: 答案错误 1012KB 7MS
测试点4: 答案错误 1536KB 8MS
测试点5: 运行超时 3548KB 995MS
测试点6: 答案错误 5160KB 55MS
测试点7: 答案错误 6248KB 78MS
测试点8: 答案错误 6772KB 125MS
测试点9: 答案错误 7476KB 101MS
测试点10: 答案错误 7500KB 101MS
*/
#include<bits/stdc++.h>
using namespace std;
int R;
int a[1003][1003];
int p[1003][1003];
int f(int n,int m){
    if(n==R){
        p[n][m]=a[n][m];
        return a[n][m];
    }
    int l1,l2; 
    if(p[n+1][m]!=0)l1=p[n+1][m];
    else l1=f(n+1,m);
    if(p[n+1][m+1]!=0)l2=p[n+1][m+1];
    else l2=f(n+1,m+1);
    p[n][m]=a[n][m]+max(l1,l2);
    return p[n][m];
}
int main(){
    cin>>R;
    for(int i=1;i<=R;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    cout<<f(1,1); 
    return 0;
}
/*
记忆化+递归100%
*/
#include<bits/stdc++.h>
using namespace std;
int R;
int a[1005][1005],dp[1005][1005];
int main(){
    cin>>R;
    for(int i=1;i<=R;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=R;i++){
        for(int j=1;j<=i;j++){
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=R;i++){
        ans=max(dp[R][i],ans);
    }
    cout<<ans;
    return 0;
}
/*
dp100%
*/

 

1271：【例9.15】潜水员  http://ybt.ssoier.cn:8088/problem_show.php?pid=1271

#include<bits/stdc++.h>
using namespace std;
int m,n,k;
int O2[1003],N2[1003],w[1003];
int f[25][85];
int main(){
    cin>>m>>n;
    cin>>k;
    memset(f,0x3f3f3f3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=k;i++){
        cin>>O2[i]>>N2[i]>>w[i];
    }
    for(int a=1;a<=k;a++){
        for(int i=m;i>=0;i--){
            for(int j=n;j>=0;j--){
                if(i>=O2[a]&&j>=N2[a])f[i][j]=min(f[i][j],f[i-O2[a]][j-N2[a]]+w[a]);
                else if(i>=O2[a])f[i][j]=min(f[i][j],f[i-O2[a]][0]+w[a]);
                else if(j>=N2[a])f[i][j]=min(f[i][j],f[0][j-N2[a]]+w[a]);
                else f[i][j]=min(f[i][j],f[0][0]+w[a]);
            }
        }
    }
    cout<<f[m][n];
    return 0;
}
/*
f[i][j]=min(f[i][j],f[i-O2[a]][j-N2[a]]+w[a]);
*/