不能颓了，得复习NOIp

屯些题目吧，FZYZOJ

现在做了：

6

update: 2015/8/30 20:17 不屯了，第一次屯，屯炸了，好累~

1004：文科生的悲哀(Matrix67)，简单递推。

1006：三取方格数，多线程DP。

# include <stdio.h>
# include <algorithm> 
using namespace std;
int f[44][22][22][22];
int n,a[22][22];
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			scanf("%d",&a[i][j]);
	//f[i,j,k,l] 走了i步，第一个人横着走了j步，第二个人横着走了k步，第三个人横着走了l步
	for (int i=1;i<=2*n;++i)
		for (int j=1;j<=i;++j)
			for (int k=1;k<=i;++k)
				for (int l=1;l<=i;++l) {
					int j2=i-j+1,k2=i-k+1,l2=i-l+1;
					f[i][j][k][l]=max(f[i-1][j][k][l], max(
					                  f[i-1][j-1][k][l], max(
					                  f[i-1][j-1][k][l-1], max(
					                  f[i-1][j-1][k-1][l], max(
					                  f[i-1][j-1][k-1][l-1], max(
					                  f[i-1][j][k][l-1], max(
					                  f[i-1][j][k-1][l], 
					                  f[i-1][j][k-1][l-1])))))));
					f[i][j][k][l]+=a[j][j2]+a[k][k2]+a[l][l2];
					if(j==k&&k==l) f[i][j][k][l]-=(a[j][j2]+a[k][k2]);
					else {
						if(j==k) f[i][j][k][l]-=a[j][j2];
						else if(k==l) f[i][j][k][l]-=a[k][k2];
						else if(j==l) f[i][j][k][l]-=a[l][l2];
					}						  
				} 
	printf("%d\n",f[2*n-1][n][n][n]); 
}

1016：三国杀1v1大赛：序列动态规划。$f[i,j]$表示前$i$次比赛，$j$个人的最小值。

需要滚动数组。

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int n,m,a[10003],i,now,last;
long long f[2][10003];
inline int cmp(int a,int b){return a>b;}
int main() {
	for(i=scanf("%d%d",&n,&m)-1;i<=m;++i) scanf("%d",&a[i]);
	sort(a+1,a+m+1,cmp);
	for(i=1,now=0,last=1;i<=n;++i) {
		now^=1,last^=1;
		memset(f[now],21444444,sizeof(f[now]));
		for (int j=3*i;j<=m;++j)
			f[now][j]=min(f[now][j-1],f[last][j-2]+1LL*(a[j]-a[j-1])*(a[j]-a[j-1]));
	} printf("%lld\n",f[now][m]);
}

1032：LCIS，经典DP，学了学，感觉很……

这题炖烂了……WA了几发，后来看了看，这是LCIS不是LIS，我写成了$a[i]!=b[j]$，………………

#include<stdio.h>
	#include<string.h> 
	using namespace std;
	int n,m1,m2,a[510],b[510],f[510]={},maxc=0;
	int main(){
		scanf("%d",&n);while(n--) {memset(f,0,sizeof(f));
			scanf("%d",&m1);for(int i=1;i<=m1;++i)scanf("%d",&a[i]);
			scanf("%d",&m2);for(int i=1;i<=m2;++i)scanf("%d",&b[i]);
			for(int i=1;i<=m1;++i){
				maxc=0;
				for(int j=1;j<=m2;++j) {
					if(a[i]>b[j]&&f[j]>maxc)maxc=f[j];
					if(a[i]==b[j])f[j]=maxc+1;
				}
			}
			maxc=0;
			for(int i=1;i<=m2;++i)if(f[i]>maxc)maxc=f[i];
			printf("%d\n",maxc);
		}
	}

2207：Zrn的骗分策略：背包变种。

#include<stdio.h>
#include<algorithm>
using namespace std;
int f[210][210],n,t,a[210][13];
//前i题，用了t分钟，最多骗分 
int main() {
	scanf("%d%d",&n,&t);
	for (int i=1;i<=n;++i)
		for(int j=1;j<=10;++j)scanf("%d",&a[i][j]);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=t;++j) {
			f[i][j]=f[i][j-1];
			for(int k=0;k<=10;++k)
				if(j>=a[i][k])f[i][j]=max(f[i][j],f[i-1][j-a[i][k]]+k*10);
		}
	printf("%d\n",f[n][t]);
}

1282: NOIP福建夏令营最大和，求个最大子段和和最小子段和，答案就是max(最大子段和，总和-最小子段和)。

#include <stdio.h>
#define max(a,b) ((a)<(b)?(b):(a))
using namespace std;
int n,m1=-2147480000,m2=2147480000,g,x=0,y=0,t;
int main() {
    scanf("%d",&n);while(n--) {
        scanf("%d",&g);t+=g;
        if(x>0)x+=g;else x=g;
        if(y<0)y+=g;else y=g;
        if(x>m1)m1=x;
        if(y<m2)m2=y; 
    }
    printf("%d\n",max(m1,t-m2));
}