给定一个由n个正整数组成的序列，从该序列中删除若干个整数，使剩下的整数 构成非升子序列（即后面的项不大于前面的项），打印出最长的非升子序列。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[100]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int b[100]={0,48,16,45,47,52,46,36,28,46,69,14,42};
a[1]=1;
int lmax=0;
for(int i=2;i<=12;i++)
{
int max=0;
for(int j=i-1;j>=1;j--)
{
if(b[i]>b[j])
{
if(a[j]>max)max=a[j];
}
}
a[i]=max+1;
if(a[i]>lmax)lmax=a[i];
}
cout<<"最长非降子序列的长度为"<<lmax<<endl;
for(int i=12;i>=1;i--)
{
if(a[i]==lmax)
{
cout<<b[i]<<",";
lmax--;
}
}
return 0;
}
已知n种物品和一个可以容纳重量c的背包，物品i的重量为wi，产生的效益为pi。在装包时物品i可以装入，也可以不装入，但不可拆开装。如何选择这n个物品，使总收益最大？
#include<bits/stdc++.h>
using namespace std;
int MAX(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n=6;//n种物品
int c=60;//可容纳重量为60的物品
int w[7]={0,15,17,20,12,9,14};//每件物品的重量
int p[7]={0,32,37,46,26,21,30};//每件物品的价值
int a[100][100];//第一【】装了多少物品，第二个【】剩余多少容量，值产生的价值
for(int i=1;i<=n;i++)//n为6
{
for(int j=1;j<=c;j++)//c为60
{
if(j>=w[i])//当前容量大于等于当前物品的容量(可以拿)
{
//可以拿的时候判断到底拿不拿
a[i][j]=MAX(a[i-1][j],a[i-1][j-w[i]]+p[i]);
}
else//当前容量小于当前物品的容量(不能拿)
{
a[i][j]=a[i-1][j];
}
}
}
cout<<"背包能装的最大价值为："<<a[n][c];
return 0;
}
在一个n位整数a中插入r个加号，将它分成r+1个整数，找出一种加号的插入方法，使得这r+1个整数的和最小
#include<bits/stdc++.h>
using namespace std;
int sub(int number[],int start,int end);
int main()
{
char character[100];
int number[100];
int addnumber;
int f[100][100];
cout<<"请输入整数：";
cin>>character;
cout<<"请输入+号的个数：";
cin>>addnumber;
int length=strlen(character);
//将字符型转化为数字型
for(int i=0;i<length;i++)
{
number[i]=character[i]-48;
}
//赋初值
for(int i=1;i<=length;i++)
{
f[i][0]=sub(number,0,i);
}
for(int i=1;i<=addnumber;i++)
{
for(int j=i+1;j<=length;j++)
{
int min=99999999;
for(int k=i;k<j;k++)
{
int value=f[k][i-1]+sub(number,k,j);
if(value<min)
{
min=value;
}
}
f[j][i]=min;
}
}
cout<<"最小值为："<<f[length][addnumber];
return 0;
}
int sub(int number[],int start,int end)
{
int count=0;
for(int i=start;i<end;i++)
{
count=count*10+number[i];
}
return count;
}
