D4代码AC集

已于 2025-03-23 12:01:05 修改
阅读量343 收藏 1
点赞数 2
文章标签： 算法 c++ 数据结构
于 2024-09-08 11:46:38 首次发布
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/CXP12636/article/details/142024358
版权

贪心问题解决的步骤：

（局部贪心能导致全局贪心）
   1.确定贪心策略
   2.验证贪心策略是否正确

排队接水

#include<bits/stdc++.h>
using namespace std;
int main(){
    int w,n,a[32000];
    cin>>w>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    int i=1,j=n;
   int cnt=0;
   while(i<=j){
       if(a[i]+a[j]<=w){
           cnt++;
           i++;
           j--;
       }
       else if(a[i]+a[j]>w){
           cnt++;
           j--;
       }
   }
   cout<<cnt;
	return 0;
}

独木舟

#include<bits/stdc++.h>
using namespace std;
struct node{
    int bh,sj;
}a[220];
int n;
bool cmp(node x,node y){
    if(x.sj==y.sj){
        return x.bh<y.bh;
    }
    else{
        return x.sj<y.sj;
    }
}
int main(){
    cin>>n; 
    double sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i].sj;
        a[i].bh=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        cout<<a[i].bh<<" ";
    }
    for(int i=1;i<=n;i++){
          sum+=(n-i+1)*a[i].sj;
    }
    cout<<endl;
    printf("%.2lf",sum/n);
	return 0;
}

删数问题

#include<bits/stdc++.h>
using namespace std;
int main(){
    int s;
    string n;
    cin>>n;
    cin>>s;
    while(s--){
        int flag=0;
    for(int i=0;i<n.size()-1;i++){
        if(n[i]>n[i+1]){
            n.erase(i,1);
            flag=1;
            break;
        }
    }
     if(flag==0){
             n.erase(n.size()-1,1);
        }
    }
    int f1=0;
    for(int i=0;i<=n.size()-1;i++){
       
        if(n[i]!='0'){
            f1=1;
        }
         if(f1==1){
            cout<<n[i];
        }
    }
    if(f1==0){
        cout<<0;
    }
	return 0;
}

最小新整数

#include<bits/stdc++.h>
using namespace std;
int main(){
    int s,t;
    string n;
    cin>>t;
    while(t--){
	    cin>>n;
	    cin>>s;
	    int l=0;
	    while(s--){
	        int flag=0; 
	         l=n.size();
	        for(int i=0;i<l-1;i++){
	            if(n[i]>n[i+1]){
		            n.erase(i,1);
		            flag=1;
		            break;
		        }
		    }
	       	if(flag==0){
	            n.erase(l-1,1);
	        }
	    }
	    int f1=0;
	    l=n.size();
	    for(int i=0;i<=l-1;i++){
	        if(n[i]!='0'){
	            f1=1;
	        }
	         if(f1==1){
	            cout<<n[i];
	        }
	    }
	    cout<<endl;
	    
    }
	return 0;
}

拦截导弹问题

#include<bits/stdc++.h>
using namespace std;
int main(){
    int cnt=0,n=1;
    int a[1100],b[1100],flag=0;
	  while(cin>>a[n]){
	      n++;
	  }
	  n--;
	  int ans=1;//共ans个系统
	  b[1]=a[1];
	  for(int i=2;i<=n;i++){
	      flag=0;
	      for(int j=1;j<=ans;j++){
	          if(b[j]>=a[i]){//能拦截
	              b[j]=a[i];
	              flag=1;
	              break;
	          }
	      }
	  if(flag==0){
	      b[++ans]=a[i];
	  }
	 }
	   cout<<ans;
	return 0;
}

区间覆盖问题 

#include<iostream>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
struct node{
    int a,b;
}x[110000];
bool cmp(node x,node y){
        return x.a<y.a;
}
int main(){
    int n,s,t;
    cin>>s>>t;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i].a>>x[i].b;
    }
    sort(x+1,x+n+1,cmp);
    int sum=s,cnt=0;
    int maxx=-inf;
    //s是起，t是终
    for(int i=1;i<=n;i++){
        int j=i;
        maxx=-inf;
        while(j<=n&&x[j].a<=s){//能覆盖起点
            maxx=max(maxx,x[j].b);
            j++;
        }
      if(maxx<s){
            cout<<"-1";
           return 0;
        }
        s=maxx;
        cnt++;
        i=j-1;
        if(maxx>=t){
            break;
        }
        
    }
    
    cout<<cnt;
    return 0;
}

整数区间

#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int a,b;
}x[110000];
bool cmp(node x,node y){
        return x.b<y.b;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i].a>>x[i].b;
    }
    sort(x+1,x+n+1,cmp);
    int sum=x[1].b,cnt=1;
    for(int i=2;i<=n;i++){
        if(x[i].a<=sum){
        continue;
        }
        else{
        cnt++;
        sum=x[i].b;
        
        }
    }
    cout<<cnt;
    return 0;
}

Crossing River

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int cnt,sum;
int a[N],n,t;
int main(){
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>n;
        sum=0;
       for(int i=1;i<=n;i++){
        cin>>a[i];
       }
       sort(a+1,a+n+1);
       while(n>3){
           sum=sum+min(a[1]*2+a[n-1]+a[n],a[2]*2+a[1]+a[n]);
           n=n-2;
       }
       if(n==1){
           sum+=a[1];
       }
       else if(n==2){
           sum+=a[2];
       }
       else if(n==3){
           sum+=a[1]+a[2]+a[3];
       }
       cout<<sum<<"\n";
    }
	return 0;
}

货仓选址

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int cnt,sum;
int a[N],n,t;
priority_queue<int>maxqp;
priority_queue<int,vector<int>,greater<int>>minqp;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxqp.push(a[i]);
        minqp.push(a[i]);
    }
    for(int i=1;i<=n/2;i++){
        int y=maxqp.top();
        maxqp.pop();
        int x=minqp.top();
        minqp.pop();
        sum+=y-x;
    }
    cout<<sum;
	return 0;
}

流水作业调度问题

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,s1,s2;
int s[N];
struct node{
    int s1,s2;
}a1[N],a2[N];
bool cmp1(node a,node b){
    return a.s1<b.s1;
}
bool cmp2(node a,node b){
    return a.s2>b.s2;
}
int main(){
    while(cin>>n&&n!=0){
      int cnt1=0,cnt2=0;
        for(int i=1;i<=n;i++){
            cin>>s1>>s2;
            if(s1<s2){
                  cnt1++;
                  a1[cnt1].s1=s1;
                  a1[cnt1].s2=s2;
            }
            else{
                cnt2++;
                a2[cnt2].s1=s1;
                a2[cnt2].s2=s2;
            }
        }
        sort(a1+1,a1+1+cnt1,cmp1);
        sort(a2+1,a2+1+cnt2,cmp2);
        for(int i=1;i<=cnt2;i++){
            a1[cnt1+i]=a2[i];
        }
        for(int i=1;i<=n;i++){
            s[i]=s[i-1]+a1[i].s1;
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(ans<s[i]){
                ans=s[i]+a1[i].s2;
            }
            else{
                ans+=a1[i].s2;
            }
        }
        cout<<ans<<"\n";
    }
	return 0;
}

耍杂技的牛 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,cnt=-1e9;
int g[N];
struct node {
	int w,s;
} a[N];
bool cmp(node x,node y) {
	return x.w+x.s<y.w+y.s;
}
int main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i].w>>a[i].s;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1; i<=n; i++) {
		g[i]=g[i-1]+a[i].w;
	}
	for(int i=1; i<=n; i++) {
		cnt=max(cnt,g[i-1]-a[i].s);
	}
	cout<<cnt;
	return 0;
}

哈夫曼树

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>>qp;
int a[1100];
int n,sum;
int main(){
    while(cin>>n){
        sum=0;
        while(qp.empty()!=1){
            qp.pop();
        }
        for(int i=1;i<=n;i++){
            cin>>a[i];
             qp.push(a[i]);
            }
            while(qp.size()>1){
                 int t=qp.top();
                 qp.pop();
                 int f=qp.top();
                 qp.pop();
                 sum+=t+f;
                 qp.push(t+f);
            }   
          cout<<sum<<"\n";
    }
	return 0;
}

supermarket

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
    int di,pi;
}a[N];
bool cmp(node x,node y){
    if(x.di==y.di){
        return x.pi>y.pi;
    }
    return x.di<y.di;
}
int n,sum;
priority_queue<int,vector<int>,greater<int>>piqp;
int main(){
    while(cin>>n&&n!=-1){
        sum=0;
        for(int i=1;i<=n;i++){
            cin>>a[i].pi>>a[i].di;
        }
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=n;i++){
            piqp.push(a[i].pi);
            if(a[i].di<piqp.size()){
                piqp.pop();
              
            }
        }
        while(piqp.empty()!=1){
            sum+=piqp.top();
                 piqp.pop();
        }
        cout<<sum<<"\n";
    }
	return 0;
}

序列合并

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
priority_queue<int>qp;
int a[N],b[N],ans[N];
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];

    }
     for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
       for(int j=1;j<=n;j++){
           if(qp.size()<n){
               qp.push(a[i]+b[j]);
           }
           else{
                  if(qp.top()>a[i]+b[j]){
                      qp.push(a[i]+b[j]);
                      qp.pop();
           }
                else{
                 break;
             }
           }
       }
    }
    for(int i=1;i<=n;i++){
        ans[i]=qp.top();
        qp.pop();
    }
    for(int i=n;i>=1;i--){
        cout<<ans[i]<<" ";
    }
	return 0;
}

合并果子

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>>qp;
int a[110000];
long long n,sum;
int main(){
         cin>>n;
        sum=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
             qp.push(a[i]);
            }
            while(qp.size()>1){
                 int t=qp.top();
                 qp.pop();
                 int f=qp.top();
                 qp.pop();
                 sum+=t+f;
                 qp.push(t+f);
            }   
          cout<<sum<<"\n";
	return 0;
}

数字三角形2

#include<bits/stdc++.h>
using namespace std;
const int N=110;
bool dp[N][N][N];
int b[N][N];
int maxx=0;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=i;j++){
          cin>>b[i][j];
      }
    }
      dp[1][1][b[1][1]%100]=1;
      for(int i=2;i<=n;i++){
          for(int j=1;j<=i;j++){
              for(int k=0;k<100;k++){
                  if(dp[i-1][j-1][k]==1||dp[i-1][j][k]==1){
                      dp[i][j][(k+b[i][j])%100]=1;
                  }
              }
          }
      }
      for(int j=1;j<=n;j++){
          for(int k=0;k<100;k++){
              if(dp[n][j][k]==1){
                  maxx=max(maxx,k);
              }
          }
      }
      cout<<maxx;
	return 0;
}

数字三角形3 

#include<bits/stdc++.h>
using namespace std;
const int N=110;
const int ans=0x3f3f3f3f;
int f[N][N];
int b[N][N];
int maxx=0,s;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=i;j++){
          cin>>b[i][j];
      }
    }
     f[1][1]=b[1][1];
    b[n/2][n/2]+=ans; 
     for(int i=1;i<=n;i++){
         for(int j=1;j<=n;j++){
             f[i][j]=max(f[i-1][j],f[i-1][j-1])+b[i][j];
         }
     }
     for(int i=1;i<=n;i++){
         maxx=max(maxx,f[n][i]);
     }
    cout<<maxx-ans;
	return 0;
}

 数字三角形4

#include<bits/stdc++.h>
using namespace std;
const int N=110;
const int ans=0x3f3f3f3f;
int f[N][N];
int b[N][N];
int maxx=0,s;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=i;j++){
          cin>>b[i][j];
      }
    }
     f[1][1]=b[1][1];
    b[n/2][n/2]+=ans; 
     for(int i=1;i<=n;i++){
         for(int j=1;j<=n;j++){
             f[i][j]=max(f[i-1][j],f[i-1][j-1])+b[i][j];
         }
     }
     for(int i=1;i<=n;i++){
         maxx=max(maxx,f[n][i]);
     }
    cout<<maxx-ans;
	return 0;
}

最大子段和

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int ans=0x3f3f3f3f;
int n,a[N],sum[N],maxx=-ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        sum[i]=max(sum[i-1],0)+a[i];
    }
    for(int i=1;i<=n;i++){
        maxx=max(maxx,sum[i]);
    }
    cout<<maxx;
    return 0;
}

 最长公共子序列

#include<bits/stdc++.h>
using namespace std;
int p[2010][2010];
string a,b;
int n;
int main(){ 
    cin>>a>>b;
    int len1=a.size();
    int len2=b.size();
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(a[i-1]==b[j-1]){
                p[i][j]=p[i-1][j-1]+1;
            }
            else {
                p[i][j]=max(p[i-1][j],p[i][j-1]);
            }
        }
    }
    cout<<p[len1][len2];
    return 0;
}

编辑距离

#include<bits/stdc++.h>
using namespace std;
string a,b;
int p[2010][2010];
int main(){
    cin>>a>>b;
    int len1=a.size();
    int len2=b.size();
    int n=max(len1,len2);
    for(int i=1;i<=len1;i++){
        p[i][0]=i;
    }
    for(int i=1;i<=len2;i++){
        p[0][i]=i;
    }
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(a[i-1]==b[j-1]){
                p[i][j]=min(p[i-1][j]+1,min(p[i][j-1]+1,p[i-1][j-1]));
            }
            else{
                 p[i][j]=min(p[i-1][j]+1,min(p[i][j-1]+1,p[i-1][j-1]+1));
            }
        }
    }
    cout<<p[len1][len2];
	return 0;
}

计算字符串距离

#include<bits/stdc++.h>
using namespace std;
int n,p[1010][1010];
string a,b;
int main(){
    cin>>n;
    while(n--){
        cin>>a>>b;
        int len1=a.size();
        int len2=b.size();
        for(int i=1;i<=len1;i++){
            p[i][0]=i;
        }
        for(int i=1;i<=len2;i++){
            p[0][i]=i;
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(a[i-1]==b[j-1]){
                    p[i][j]=min(p[i-1][j]+1,min(p[i][j-1]+1,p[i-1][j-1]));
                }
                else{
                    p[i][j]=min(p[i-1][j]+1,min(p[i][j-1]+1,p[i-1][j-1]+1));
                }
            }
        }
        cout<<p[len1][len2]<<"\n";
    }
    return 0;
}

最长公共上升子序列

#include<bits/stdc++.h>
using namespace std;
int n,f[3010][3010];
int a[3010],b[3010];
int main(){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=n;i++){
            cin>>b[i];
        }
        for(int i=1;i<=n;i++){
            int maxk=1;
            for(int j=1;j<=n;j++){
                if(a[i]!=b[j]){
                    f[i][j]=f[i-1][j];
                }
                if(a[i]==b[j]){
                    f[i][j]=max(maxk,1);
                }
                if(b[j]<a[i]){
                    maxk=max(maxk,f[i-1][j]+1);
                }
                }
            }

         int ans=0;
               for(int i=1;i<=n;i++){
                    ans=max(f[n][i],ans);
               }
        cout<<ans;
    return 0;
}

01背包问题

 （普通）

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N][N];
//用dp[n][m]来表示有N个物品时放入容量为m的背包所获得的最大价值;
int n,m,w[N],c[N];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>c[i];
    }
    for(int i=1;i<=n;i++){//每件物品
        for(int j=1;j<=m;j++){//容量
            if(j>=w[i]){//当物品可以选时
                 dp[i][j]=max(dp[i-1][j-w[i]]+c[i],dp[i-1][j]);
                //  选或不选
            }
            else{
                dp[i][j]=dp[i-1][j];//容量不够时，只能继承上一个最大值
            }
        }
    }
    cout<<dp[n][m];//输出最大值
    return 0;
}

（滚动数组优化）

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N];//行只用一行
//用dp[n][m]来表示有N个物品时放入容量为m的背包所获得的最大价值;
int n,m,w[N],c[N];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>c[i];
    }
    for(int i=1;i<=n;i++){//滚动更新n次
        for(int j=m;j>=w[i];j--){//j从后往前,在m和w[i]之间才执行,省掉一个判断
                 dp[j]=max(dp[j-w[i]]+c[i],dp[j]);
        }
    }
    cout<<dp[m];
    return 0;
}

 数字组合

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N][N],n,m,ans,a[N];
//dp[n][m]为n个数和为m时的方案数
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
   for(int i=0;i<=n;i++){//初始化,和为0也是一种方案
       dp[i][0]=1;
   }
    for(int i=1;i<=n;i++){//枚举方案数
      for(int j=1;j<=m;j++){
          if(j>=a[i]){//当可以选
              dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];
              //和为i时方案数为选这个数的方案数加不选这个数的方案数
          }
          else{//当不可以选
              dp[i][j]=dp[i-1][j];
              //和为上一个数的方案数
          }
      }
    }
        cout<<dp[n][m];
    return 0;
}

完全背包问题

1

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N];
int n,m,w[N],c[N];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>c[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
        for(int k=0;k*w[i]<=j;k++){//再来一层循环枚举数量(其他如01)
            dp[j]=max(dp[j-w[i]*k]+k*c[i],dp[j]);
            }
        }
    }
    cout<<"max="<<dp[m];
    return 0;
}

2

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N];
int n,m,w[N],c[N];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>c[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=w[i];j<=m;j++){
            dp[j]=max(dp[j-w[i]]+c[i],dp[j]);
            //将倒序循环替换成正序循环,让每一个物品在最优时枚举多次
            //（因为前面选择了，后面还会选择）
        }
    }
    cout<<"max="<<dp[m];
    return 0;
}

多重背包

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N][N],n,m,w[N],c[N],s[N];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>c[i]>>s[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
            for(int k=0;k*w[i]<=j&&k<=s[i];k++){
                //k枚举选举的个数,从0—k*w[i]&&s[i](不能超过j,也不能超过它的个数)
                if(j>=w[i]*k){
                    dp[i][j]=max(dp[i-1][j-k*w[i]]+k*c[i],dp[i][j]); 
                    //if能成立很多次,每次都要保留使价值最大的k(个数),所以需要和dp[i][j]本身比
                }
            }
        }
    }
    cout<<dp[n][m];
    return 0;
}

买书

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,dp[N],a[5];
int main(){
	a[1]=10;
	a[2]=20;
	a[3]=50;
	a[4]=100;
    cin>>n;
    dp[0]=1;
   for(int i=1;i<=4;i++){
   	for(int j=1;j<=n;j++){
   		   if(j>=a[i]){
   		   	dp[j]=dp[j]+dp[j-a[i]];
			}
			else{
				dp[j]=dp[j];
		 }
	   }
   }
   cout<<dp[n];
    return 0;
}

多重背包2

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int w[N],c[N],p[N],dp[N],jia,zhong,jian,cnt;
int n,m;
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>zhong>>jia>>jian;
        if(jian==0){//将完全背包转换成01背包；
            jian=m/zhong;
        }
        int x=1;
        while(jian>=x){
            w[++cnt]=zhong*x;
            c[cnt]=jia*x;
            jian-=x;
            x*=2;
        }
        if(jian>0){
            w[++cnt]=zhong*jian;
            c[cnt]=jia*jian;
        }
    }
    for(int i=1;i<=cnt;i++){
        for(int j=m;j>=w[i];j--){
            dp[j]=max(dp[j-w[i]]+c[i],dp[j]);
        }
    }
    cout<<dp[m];
    return 0;
}

分组背包

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
//f[i][j]为前i组物品,最大价值为j
int n,m,t;
int w[N],c[N],p[N],dp[N][N];
int main(){
    cin>>m>>n>>t;//输入先容量(m),再物品数量(n),还有t
    for(int i=1;i<=n;i++){
        cin>>w[i]>>c[i]>>p[i];
    }
    for(int i=1;i<=t;i++){
        for(int j=m;j>=1;j--){//二维数组1-m遍历
          dp[i][j]=dp[i-1][j];//第i组不选
            for(int k=1;k<=n;k++){//第i组选
                if(p[k]==i&&j>=w[k]){//如果ta是这一&&剩余容量够减
              dp[i][j]=max(dp[i][j],dp[i-1][j-w[k]]+c[k]);
             }
            }

        }
    }
    cout<<dp[t][m];
    return 0;
}

二维费用的背包问题

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,t;
int w[N],v[N],c[N],f[N][N];//f[价值][重量][体积]
//1.f[i][j]=f[j](压维)
//2.f[j][k](添加体积维度)
int main(){
    cin>>n>>t>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i]>>c[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){//j:m-w[i]
            for(int k=t;k>=v[i];k--){//k:t-v[i]保证下标不为负
                f[j][k]=max(f[j][k],f[j-w[i]][k-v[i]]+c[i]);
            }
        }
    }
    cout<<f[m][t];
    return 0;
}

石子合并<1>

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int ans=0x3f3f3f3f;
int a[N],df[N][N],dp[N][N],sum[N];
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    for(int len=2;len<=n;len++){//区间一共最少两个长度
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            dp[i][j]=-ans;
            df[i][j]=ans;
            for(int k=i;k<j;k++){
               dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
               df[i][j]=min(df[i][j],df[i][k]+df[k+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    cout<<df[1][n]<<"\n"<<dp[1][n];
    return 0;
}

石子合并<2>

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int anf=0x3f3f3f3f;
int dp[N][N],df[N][N],sum[N],n,a[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
       a[n+i]=a[i];//原数组复制两份
    }
   for(int i=1;i<=2*n;i++){
       sum[i]=sum[i-1]+a[i];
   }
   for(int len=2;len<=n;len++){//求有n个长度的区间
       for(int i=1;i+len-1<=2*n-1;i++){
           int j=len+i-1;
           df[i][j]=anf;
           dp[i][j]=-anf;
           for(int k=i;k<j;k++){
               dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
               df[i][j]=min(df[i][j],df[i][k]+df[k+1][j]+sum[j]-sum[i-1]);
           }
       }
   }
   int maxx=-anf,minn=anf;
   for(int i=1;i<=n;i++){//枚举长度
       maxx=max(maxx,dp[i][n+i-1]);//j是通过长度计算出来的  
       minn=min(minn,df[i][n+i-1]);
   }
   cout<<minn<<"\n"<<maxx;
    return 0;
}

 矩阵连乘

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int anf=0x3f3f3f3f;
int n,a[N],dp[N][N],b;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b;
    }
    a[++n]=b;//n个珠子有n+1个数
    for(int len=3;len<=n;len++){//用珠子代表矩阵
        for(int i=1;i+len-1<=n;i++){
            int j=len+i-1;
            dp[i][j]=anf;
            for(int k=i+1;k<i+len-1;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]);
            }
        }
    }
  cout<<dp[1][n];
    return 0;
}

能量项链

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int anf=0x3f3f3f3f;
int n,a[N],dp[N][N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    for(int len=3;len<=n+1;len++){//枚举数字，不是珠子
        for(int i=1;i+len-1<=n*2;i++){
            int j=len+i-1;
            dp[i][j]=-anf;
            for(int k=i+1;k<j;k++){
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]);
            }
        }
    }
    int maxx=-anf;
    for(int i=1;i<=n+1;i++){//数字长度为n+1
        maxx=max(maxx,dp[i][i+n]);
    }
    cout<<maxx;
    return 0;
}

合唱队形

#include<bits/stdc++.h>
using namespace std;
const int ans=0x3f3f3f3f;
int cnt,cntb,b[210],sumb[210],sum[210],maxx=-ans,maxxb=-ans;
//求区间终点为i的正序和倒序的长度和
int n,a[120];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[n-i+1]=a[i];
    }
    for(int i=1;i<=n;i++){
        cnt=0;
        for(int j=1;j<=i-1;j++){
            if(a[j]<a[i]){
                cnt=max(sum[j],cnt);
            }
        } 
        sum[i]=cnt+1;
    }
    for(int i=1;i<=n;i++){
        cntb=0;
        for(int j=1;j<=i-1;j++){
            if(b[j]<b[i]){
                cntb=max(sumb[j],cntb);
            }
        }
         sumb[i]=cntb+1;
    }
    int maxxn=-ans;
    for(int i=1;i<=n;i++){
        maxxn=max(maxxn,sum[i]+sumb[n-i+1]-1);
       //因为sunb是倒序存储，下标要换成n-i+1才和sum[i](正序)相同
       //（存的时候是那样存的）
        
    }
    cout<<n-maxxn;
    return 0;
}

大盗阿福

#include<bits/stdc++.h>
using namespace std;
int n,t,a[101000],dp[101000][2];
int main(){
    cin>>t;
    for(int k=1;k<=t;k++){
        int maxx,cnt;
        //初始化
        for(int i=1;i<=n;i++){
            for(int j=1;j<=2;j++){
                dp[i][j]=0;
            }
        }
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        //用0和1来表示这个店铺有没有洗劫过
        for(int i=1;i<=n;i++){
                dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
                 //当前不选，（关于上一家店铺）有两种可能：
                 //1.上一家洗劫过，2.上一家店铺没有洗劫过
                 //找一个最大值
                dp[i][1]=max(dp[i-1][0],dp[i-1][0]+a[i]);
                 //因为洗劫这家店铺需要上家没有洗劫，只有一种可能
           }
           maxx=max(dp[n][0],dp[n][1]);
           cout<<maxx<<"\n";
        }
    return 0;
}

CSP-J2019第二轮认证T3-纪念品

#include<bits/stdc++.h>
using namespace std;
int t,n,m,a[1100][1100],dp[11000];
int main(){//完全背包：无限拿 
    //背包容量是初始钱数m
    //物品重量是纪念品价值
    //物品价值是纪念品能创造的最大收益：同一物品今天的价格和明天价格的差
    cin>>t>>n>>m;
    for(int i=1;i<=t;i++){
       for(int j=1;j<=n;j++){
           cin>>a[i][j];
       }
    }
       for(int k=1;k<t;k++){//k<t:最后一天不做买入
        memset(dp,0,sizeof dp);
           for(int i=1;i<=n;i++){
              for(int j=a[k][i];j<=m;j++){
             dp[j]=max(dp[j],dp[j-a[k][i]]+a[k+1][i]-a[k][i]);  
           }
          }
          m+=dp[m];
       }
       cout<<m;
    return 0;
}

 股票买卖II

#include<bits/stdc++.h>
using namespace std;
int n,a[110000],dp[110000][2];
//dp[i][0]:第i天手里有股票，dp[i][1]:第i天手里没有股票
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dp[1][0]=0;//当第一天不买股票时，收益是0
    dp[1][1]=-a[1];//当第一天买股票时，收益是负的第一天的股票价格
    //（因为没有收益又买了股票）
    for(int i=2;i<=n;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i]);
        //dp[i-1][1]+a[i]:昨天有股票但今天卖了
        dp[i][1]=max(dp[i-1][1],dp[i-1][0]-a[i]);
        //dp[i-1][0]-a[i]:昨天没有股票但今天买了
    }
    cout<<dp[n][0];//最后一天不能有股票，不然亏钱
    return 0;
}

股票买卖III

#include<bits/stdc++.h>
using namespace std;
int n,dp[110000][5],a[110000];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dp[1][1]=dp[1][3]=-a[1];//没有收益，要亏钱
    for(int i=2;i<=n;i++){
       dp[i][0]=dp[i-1][0];//没股票
       dp[i][1]=max(dp[i-1][1],dp[i-1][0]-a[i]);//有股票
       dp[i][2]=max(dp[i-1][2],dp[i-1][1]+a[i]);//卖出过，现在没股票
       dp[i][3]=max(dp[i-1][3],dp[i-1][2]-a[i]);//卖出过，现在有股票
       dp[i][4]=max(dp[i-1][4],dp[i-1][3]+a[i]);//两次买卖都进行完了
       //从上面的两种情况推过来：1.按照原来的1状态  2.买入或卖出
    }
    cout<<max(dp[n][0],max(dp[n][2],dp[n][4]));
    //因为两次买卖不用进行完，所以要把每个手里没有股票的情况都考虑一遍（有股票就亏）
    return 0;
}

 股票买卖IV

#include<bits/stdc++.h>
using namespace std;
int n,a[110000],dp[110000][210],k;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
       for(int j=1;j<=2*k;j++){
           if(j%2!=0){
            dp[1][j]=-a[1];
        }
       }
    for(int i=2;i<=n;i++){
        dp[i][0]=dp[i-1][0];
        for(int j=1;j<=2*k;j++){
            if(j%2!=0){//奇数买入偶数卖出 
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-a[i]);
                //dp[i-1][j-1]:第j个状态是由第j-1个状态推过来的 
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+a[i]);
            }
        }
    }
    int maxx=-0x3f3f3f3f;
        for(int j=0;j<=k*2;j+=2){
        maxx=max(maxx,dp[n][j]);
      }
    cout<<maxx;
    return 0;
}

冰原狼

#include<bits/stdc++.h>
using namespace std;
const int ans=0x3f3f3f3f;
int n,t,a[210],b[210],df[210][210],cnt;
//区间DP
int main(){
    cin>>t;
    for(int p=1;p<=t;p++){
        cnt++;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=n;i++){
            cin>>b[i];
        }
        for(int i=1;i<=n;i++){
            df[i][i]=a[i]+b[i-1]+b[i+1];
         //初始化，杀死第i头狼需要接受第i头狼的攻击值和它两边狼的附加攻击值
        }
        for(int len=2;len<=n;len++){
            for(int i=1;i+len-1<=n;i++){
                int j=i+len-1;
                df[i][j]=ans;
                for(int k=i;k<=j;k++){
                  //k表明在这个区间内，第k头狼最后被杀死
                    df[i][j]=min(df[i][j],df[i][k-1]+df[k+1][j]+b[i-1]+b[j+1]+a[k]);
                    //杀死第k头狼意味着当前区间内它两边的所有狼都已经被杀死了（因为这样杀死它所 
                    //受攻击值最小）
                    //杀死第k头狼最小需要接受杀死它两边狼所需接受的最小攻击值加上这头狼的攻击值
                    //加上这头狼现在两边的狼的附加攻击值
                }
            }
        }
        cout<<"Case #"<<cnt<<": "<<df[1][n]<<"\n"; 
        for(int i=1;i<=n;i++){//初始化
            b[i]=0;
            a[i]=0;
            for(int j=1;j<=n;j++){
                df[i][j]=0;
            }
        }
    }
    return 0;
}

自然数的拆分求方案数

#include<bits/stdc++.h>
using namespace std;
long long n,a[4100],dp[4100];
//完全背包的思想
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        a[i]=i;//把从1~n-1的数当成重量，把n当成背包容量
    }
    dp[0]=1;//有0个物品时方案数是1种（不选）
    for(int i=1;i<n;i++){//压维
        for(int j=a[i];j<=n;j++){
            dp[j]=dp[j]%2147483648+dp[j-a[i]]%2147483648;
       //当前方案数之和是选这个数与不选这个数的方案数的和
        }
    }
    cout<<dp[n]%2147483648;
    return 0;
}

CSP-J2020第二轮认证T4-方格取数

#include<bits/stdc++.h>
using namespace std;
long long n,m,dp[1100],df[1100],a[1100][1100],dz[1100][1100];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dz[i][j]=-0x3f3f3f3f;
            a[i][j]=-0x3f3f3f3f;//保证起点是左上角，不在地图外转移
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    dz[1][1]=a[1][1];
    for(int i=2;i<=n;i++){
        dz[i][1]=dz[i-1][1]+a[i][1];
    }
    //dp[i]表示从上到下走到i,j的最大值 
	// df[i]表示从下到上走到i,j的最大值 
        for(int j=2;j<=m;j++){//一列列枚举 
            dp[1]=dz[1][j-1]+a[1][j];//因为从左边 来的数在以前dz算好了 
            for(int i=2;i<=n;i++){
                dp[i]=max(dz[i][j-1],dp[i-1])+a[i][j];
            }
            df[n]=dz[n][j-1]+a[n][j];
            for(int i=n-1;i>=1;i--){
                df[i]=max(dz[i][j-1],df[i+1])+a[i][j];
            }
            for(int i=1;i<=n;i++){
                dz[i][j]=max(dp[i],df[i]);
            }
        }
        cout<<dz[n][m];
    return 0;
}

加分二叉树

#include<bits/stdc++.h>
using namespace std;
//考虑中序遍历，分割点k就是根
long long tree[1100][1100];//记录每个区间的根
long long n,a[1100],dp[1100][1100];
void qian(int l,int r){
    if(l>r){
        return ;
    }
    cout<<tree[l][r]<<" ";
    qian(l,tree[l][r]-1);
    qian(tree[l][r]+1,r);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        tree[i][i]=i;
        dp[i][i]=a[i];
        dp[i-1][i]=dp[i][i-1]=1;//空区间赋值
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=len+i-1;
            for(int k=i;k<=j;k++){
                
                if(dp[i][j]<dp[i][k-1]*dp[k+1][j]+a[k]){
                    dp[i][j]=dp[i][k-1]*dp[k+1][j]+a[k];
                    tree[i][j]=k;//i-j中序遍历的根是k;
                }
            }
        }
    }
    cout<<dp[1][n]<<"\n";
    qian(1,n);//最大的数的前序遍历是1-n
    return 0;
}

货币系统

#include<bits/stdc++.h>
using namespace std;
int  t,n,m,a[11000],f[41000];
int main() {
	cin>>t;
	for(int p=1;p<=t;p++){
		cin>>n;
		memset(f,0,sizeof f);
		int maxx=0,cnt=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			maxx=max(maxx,a[i]);
		}
		f[0]=1;
		for(int i=1;i<=n;i++){
			for(int j=a[i];j<=maxx;j++){
				f[j]=f[j]+f[j-a[i]];
			}
		}
		for(int i=1;i<=n;i++){
			if(f[a[i]]==1){
				cnt++;
			}
		}
		cout<<cnt;
	}
	return 0;
}

自然数的拆分求方案数

#include<bits/stdc++.h>
using namespace std;
const long long ans=2147483648;
long long f[4100],a[4100],n;
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        a[i]=i;
    }
    f[0]=1;//可以拆分成它本身
    for(int i=1;i<n;i++){//i<n:不能拆成它本身 
        for(int j=a[i];j<=n;j++){
            f[j]=(f[j]+f[j-a[i]])%ans;
        }
    }
    printf("%lld",f[n]);
     return 0;
}

插入排序

1.原代码

#include<bits/stdc++.h>
using namespace std;
int a[11000],q,b[11000],n,flag,cnt;
void pai(int x){
	for(int i=1;i<=n;i++){
		b[i]=a[i];
	}
for (int i=1;i<=n;i++){
    for (int j=i;j>=2;j--){
        if(j==x){
        	flag=2;
        	//cout<<j<<" "; 
		  }
		  if(j-1==x){
		  	flag=1;
		  }
        if ( b[j] < b[j-1] ){
            int t = b[j-1];
            b[j-1] = b[j];
            b[j] = t;	
            
           // cout<<"排序:"<<b[j]<<" "<<b[j-1]<<"\n";
        }
		cout<<flag<<":";
		if(flag==1||flag==2){
				cnt=j-flag+1;
				//cout<<j<<": "<<flag<<"\n";
				//cout<<cnt<<"\n"; 
				flag=0;
			}
		for(int i=1;i<=n;i++){
            	cout<<b[i]<<" ";
		}
		cout<<cnt;
		cout<<"\n"; 
    }
}
cout<<cnt<<" "<<a[x]<<" "<<b[cnt]<<"\n"; 
//for(int i=1;i<=n;i++){
	//cout<<b[i]<<" ";
//}
//cout<<"\n"; 
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int p=1;p<=q;p++){
        int op,x,y;
        cout<<"输入："; 
         cin>>op;
        if(op==1){
           cin>>x>>y;
           a[x]=y;
        }
        else{
            cin>>x;
            pai(x);
        }
    }
    return 0;
}

2.正解

#include<bits/stdc++.h>
using namespace std;
int n,q,t[110000];
pair<int,int>a[110000];
int main(){
    scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){//预处理，将a数组原始位置和排序后位置先存好
		cin>>a[i].first;
		a[i].second=i;
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		t[a[i].second]=i;//t[x]=i:原始下标是x的数排序后在y下标
	}
	for(int u=1;u<=q;u++){
		int op,x,y;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d",&x,&y);
           a[t[x]].first=y;//把排序后现在位置的x改成y
           sort(a+1,a+n+1);//维护数组
           for(int i=1;i<=n;i++){
           	  t[a[i].second]=i;//重新更新
		   }
		}
		else{
			scanf("%d",&x);
			printf("%d\n",t[x]);
		}
	}
     return 0;
}

自然数的拆分

#include<bits/stdc++.h>
using namespace std;
//递归
int n,dg[11000];
void dfs(int m,int dqs) {
	for(int i=dg[dqs-1]; i<=m; i++) {
		if(i!=n) { //不能拆分成自己
			dg[dqs]=i;
			m-=i;
			if(m==0) { //拆完了
				cout<<dg[1];
				for(int j=2; j<=dqs; j++) {
					cout<<"+"<<dg[j];
				}
				cout<<"\n";
			} else {
				dfs(m,dqs+1);//如果没拆完，继续递归
			}
			m+=i;//回溯
		}
	}
}
int main() {
	scanf("%d",&n);
	dg[0]=1;//赋初值
	dfs(n,1);
	return 0;
}

CSP12636
关注
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值