最大子矩阵和

http://www.51nod.com/tutorial/course.html#!courseId=8
一个M*N的矩阵，矩阵中有一些整数（有正有负），找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的，输出这个最大的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define MAX 500+5
#define INF 0x3f3f3f3f
int  a[MAX][MAX];
long long f[MAX][MAX],d[MAX],ans=-INF;
int main(){
	freopen("yzhid.in", "r", stdin);
	int m,n;
	scanf("%d %d",&m,&n);
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
		}
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			for(int h=1;h<=m;h++){
				long long  t=f[j][h]-f[i-1][h]-f[j][h-1]+f[i-1][h-1];
				d[h]=max(d[h-1]+t,t);
				ans=max(ans,d[h]);
			}
	printf("%lld",ans);
	return 0;
}

循环数组最大字段和

http://www.51nod.com/tutorial/course.html#!courseId=9
N个整数组成的循环序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值（循环序列是指n个数围成一个圈，因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列）。当所给的整数均为负数时和为0。例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define MAX 50000+5
#define INF 0x3f3f3f3f
int a[MAX];
long long ma=-INF,mi=INF,tmax=-INF,tmin=INF,sum=0;
int  main(){
	freopen("yzhid.in","r",stdin);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	for(int i=1;i<=n;i++){
		ma=max(ma,(long long)0)+a[i];
		tmax=max(tmax,ma);
		mi=min(mi,(long long)0)+a[i];
		tmin=min(tmin,mi);
	}
	printf("%lld",max(sum-tmin,tmax));
	return 0;
}

多重背包问题

http://www.51nod.com/tutorial/course.html#!courseId=10
一个背包，承量有限为W，有n种物体，第i种物体，价值Vi，占用重量为 Wi，且有Ci件，选择物品若干放入背包，使得总重量不超过背包的承重。总价值最大？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#define INF 0x3f3f3f3f
#define MAX 50000+5
typedef long long ll;

int n,v;
int wi[105],pi[105],ci[105];
ll f[MAX];

void ZeroOnePack(ll *f,int c ,int w ){
	for(int i=v;i>=c;i--)
		f[i]=max(f[i],f[i-c]+w);
}
void CompletePack(ll *f,int c ,int w ){
	for(int i=c;i<=v;i++)
		f[i]=max(f[i],f[i-c]+w);
} 
void MultiplePack(ll *f,int c ,int w ,int m){
	if(c*m>v){
		CompletePack(f, c ,w );
		return ;
	}
	int k=1;
	while(k<m){
		ZeroOnePack(f, k*c ,k*w );
		m-=k;
		k*=2;
	}
	ZeroOnePack(f, m*c ,m*w );
} 
int main(){
	freopen("yzhid.in","r",stdin);
	scanf("%d %d",&n,&v); 
	for(int i=1;i<=n;i++)
		scanf("%d %d %d",&wi[i],&pi[i],&ci[i]); 
	for(int i=1;i<=n;i++){
		MultiplePack(f,wi[i] ,pi[i] ,ci[i]);
	}
	printf("%lld",f[v]);
	return 0;
}

更难的矩阵取数问题

http://www.51nod.com/tutorial/course.html#!courseId=11
给定一个m行n列的矩阵，矩阵每个元素是一个正整数，你现在在左上角（第一行第一列），你需要走到右下角（第m行，第n列），每次只能朝右或者下走到相邻的位置，不能走出矩阵。然后再从右下角返回到左上角，这时只能朝上或者左走，两次如果经过同一个格子，则该数字只计算一次，所有走过的数的总和作为你的得分，求最大的得分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#define INF 0x3f3f3f3f
typedef long long ll;
#define MAX 10000+10
int m,n,a[201][201];
ll  f[410][201][201];
int  main(){
	freopen("yzhid.in","r",stdin);
	scanf("%d %d",&m,&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
				scanf("%d",&a[i][j]);
	ll ans=0;
	for(int step=1;step<=m+n-1;step++){
		int start=step>n?step-n+1:1,end=step>m?m:step;
		for(int x1=start;x1<=end;x1++)
			for(int x2=start;x2<=end;x2++){
				int t=max(f[step-1][x1-1][x2],max(f[step-1][x1-1][x2-1],max(f[step-1][x1][x2-1],f[step-1][x1][x2])));
				if(x1==x2)
					f[step][x1][x2]=t+ a[step+1-x1][x1] ;
				else 
					f[step][x1][x2]=t+ a[step+1-x1][x1] + a[step+1-x2][x2];
			}
	}
	
	printf("%lld",f[m+n-1][m][m]);
	return 0;
}

最长单增子序列

http://www.51nod.com/tutorial/course.html#!courseId=12
(LIS Longest Increasing Subsequence)给定一个数列，从中删掉任意若干项剩余的序列叫做它的一个子序列，求它的最长的子序列，满足子序列中的元素是单调递增的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#define MAX 50000+5 
#define INF 0x3f3f3f3f
int a[MAX],f[MAX];
int bs(int *a,int len,int x){
	int b=0,e=len,mid;
	while(b<len){
		mid=(b+len)/2;
		if(a[mid]<x) b=mid+1;
		else len=mid; 
	}
	return a[b]>=x?b-1:b;
}
int main(){
	freopen("yzhid.in", "r", stdin);
	int n,m=1;//m:f's length
	scanf("%d",&n); 
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	f[0]=-INF;f[1]=a[1];
	for(int i=1;i<=n;i++){
		int x=bs(f,m,a[i]);
		f[x+1]=a[i];
		m=max(m,x+1);
	}
	printf("%d",m);
	return 0;
}

子序列的个数

http://www.51nod.com/tutorial/course.html#!courseId=15
给定一个正整数序列，序列中元素的个数和元素值大小都不超过105, 求其所有子序列的个数。注意相同的只算一次：例如 {1,2,1}有子序列{1} {2} {1,2} {2,1}和{1,2,1}。最后结果对10^9 + 7取余数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define MAX 100000+10
typedef long long ll;
#define MOD 1000000007
int a[MAX],h[MAX];
ll d[MAX];
int main(){
	freopen("yzhid.in","r",stdin);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	d[0]=1;h[0]=0;
	for(int i=1;i<=n;i++){
		d[i]=(d[i-1]*2)%MOD;
		if(h[a[i]]>0){
			d[i]=(MOD+d[i]-d[h[a[i]]-1])%MOD;	
		}
		h[a[i]]=i;
	}
	printf("%lld",d[n]-1);
	return 0;
}