1.最大子段和
int a[N];
int maxn(int n)
{int temp=a[0];int ans=0;ans=max(temp,ans);for(int i=1;i<n;++i){if(temp>=0){temp+=a[i];}else temp=a[i];ans=max(temp,ans);}return ans;
}
int main()
{int n,ans=0;cin>>n;for(int i=0;i<n;++i) cin>>a[i];ans=maxn(n);cout<<ans;return 0;
}2.
int main()
{string a,b;cin>>a>>b;if(a.length()>b.length()) swap(a,b);int l1=a.length(),l2=b.length();int start=0,maxn=0;int dp[l2+1][l2+1];for(int i=0;i<l1;++i) dp[i][0]=0;for(int j=0;j<l2;++j) dp[0][j]=0;for(int i=1;i<=l1;++i){for(int j=1;j<=l2;++j){if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1;if(dp[i][j]>maxn){maxn=dp[i][j];start=i-maxn;}}}cout<<maxn<<" ans:"<<a.substr(start,maxn);return 0;
}
3.
#include<iostream>
#include<stdio.h>
using namespace std;void Knapsack(int n,int c,int *w,int *p){int f[100][100];int i=0,j=0;for(i=1;i<=n;i++){for(j=1;j<=c;j++){f[i][j]=f[i-1][j];if(j>=w[i]){f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+p[i]);}}}cout<<"背包能装的最大价值是：" << f[i-1][j-1] <<endl;
}
int main(){int n;int c;int w[100]; int p[100];cout << "请输入背包容量c："<< endl;cin >>c;cout <<"请输入物体个数n："<<endl;cin >>n;for(int i=1;i<=n;i++) {cout<<"请输入物重w["<<i<<"]："<<endl;cin >> w[i]; }for(int i=1;i<=n;i++) {cout<<"请输入物价p["<<i<<"]："<<endl;cin >> p[i];}Knapsack(n,c,w,p);} 4.
typedef struct{char name;float v;float w;float key;
}goods;
int n;vector<goods> g;
float nowweight=0;
float remainweight=10;
float nowvalue=0;
vector<int> bagG;
float bestV=0;
vector<int> bestS;
float shangjie=0;
void digui(int k)
{int i,j=0,maxG;float shangjie=0;if(k>n) {if(nowvalue> bestV){for(int i=0;i<n;i++){bestS[i]=bagG[i];}bestV=nowvalue; } return; }maxG=remainweight/g[k].w;shangjie=nowvalue+(remainweight-nowweight)*g[k].key;if(bestV>=shangjie)return;for(i=maxG;i>=0;i--){if(nowweight+i*g[k].w <=remainweight ){nowweight += i*g[k].w;nowvalue+=i*g[k].v;bagG[k]=i;j=k;if(nowweight==remainweight){for(j++;j<n;j++){bagG[j]=0;}} digui(j+1);nowweight -= i*g[k].w;nowvalue-=i*g[k].v;bagG[k]=0;}}
}int main()
{cin>>n;for(int i=0;i<n;++i){cin>>g[i].name>>g[i].w>>g[i].v;}for(int i=0;i<n;i++)g[i].key= 1.0*g[i].v/g[i].w; for(int i=0;i<n-1;i++){for(int j=0;j<i;j++)if(g[j].key < g[j+1].key ){char tname=g[j].name;g[j].name=g[j+1].name;g[j+1].name=tname;float t=g[j].v;g[j].v=g[j+1].v;g[j+1].v=t;t=g[j].w;g[j].w=g[j+1].w;g[j+1].w=t;t=g[j].key;g[j].key =g[j+1].key ;g[j+1].key =t;}} for(int i=0;i<n;i++){cout<<g[i].name<<endl;}digui(0);cout<<bestV<<endl;for(int i=0;i<n;i++){cout<<g[i].name <<":"<< bestS[i]<<endl;}return 0;
}
