CSP-J 练习信心赛1 赛后总结&参考代码

#include <cstdio>
int mx(int a, int b) {
	return a>b ? a : b;
} //闲得无聊，节约时间，自己写max可以更快 
int main() {
//	freopen("expression.in", "r", stdin);
//	freopen("expression.out", "w", stdout);
	int t, a, b, c;
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d %d", &a, &b, &c); //输入3个数 
		int ans=a+b+c; //答案初始值 
		ans=mx(ans, (a+b)*c);
		ans=mx(ans, a+b*c);
		ans=mx(ans, a*b+c);
		ans=mx(ans, a*(b+c));
		ans=mx(ans, a*b*c);
		//以上是6种不同情况，注意：不能改变a,b,c的顺序！ 
		printf("%d\n", ans);
	}
	return 0;
}

#include <cstdio>
#include <cstring>
typedef long long ll;
const int N=20;
int a[N];
ll dp[N][N]; //dp[i][j]表示从i到j这个区间的最大数值
inline ll mx(ll a, ll b) {
	return a>b ? a : b;
} //此处需自己写max，因为系统自带的max无法对long long型的数字进行比较
ll dfs(int l, int r) { //区间DP,记忆化搜索
	if (dp[l][r]!=-1) return dp[l][r]; //记忆化，已经计算过
	if (l==r) return dp[l][r]=a[l]; //左端点和右端点相等的情况
	ll tp=-1; //tp临时值，表示答案
	for (int i=l; i<r; i++) {
		tp=mx(tp, dfs(l, i)+dfs(i+1, r)); //加的情况
		tp=mx(tp, dfs(l, i)*dfs(i+1, r)); //乘的情况
	}
	return dp[l][r]=tp; //返回dp[l][r]
}
int main() {
//	freopen("exp.in", "r", stdin);
//	freopen("exp.out", "w", stdout);
	int t, n;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i=0; i<n; i++)
			scanf("%d", &a[i]); //输入a[i]
		memset(dp, -1, sizeof(dp)); //清空dp数组
		printf("%lld\n", dfs(0, n-1)); //用搜索解决
	}
	return 0;
}

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=400010;
struct Build {
	int f, id; //起止标示，id号
	ll p, len; //点及长度
} b[N];
ll dp[N]; //dp[i]表示到第i段到的最长值
bool cmp(Build u, Build v) {
	if (u.p==v.p) return u.f<v.f;
	return u.p<v.p;
} //对所有的点排序
void in(ll &x) {
	char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	for (x=0; c>='0' && c<='9'; c=getchar())
		x=x*10+c-'0';
} //快读
int main() {
//	freopen("build.in", "r", stdin);
//	freopen("build.out", "w", stdout);
	int t;
	scanf("%d", &t);
	while (t--) {
		ll n, x, y;
		int k;
		scanf("%lld %d", &n, &k);
		for (int i=1; i<=k; i++) {
			//scanf("%lld %lld", &x, &y);
			in(x), in(y);
			b[i*2-1].f=0;
			b[i*2-1].p=x;
			b[i*2-1].id=i;
			b[i*2-1].len=y-x+1;
			//拆分后的第i段的第1个点 （左端点） 
			b[i*2].f=1;
			b[i*2].p=y;
			b[i*2].id=i;
			b[i*2].len=y-x+1;
			//拆分后的第i段的第2个点（右端点） 
		} //读取k段，然后进行拆分（一段拆成两个点） 
		sort(b+1, b+2*k+1, cmp); //对所有的点排序 （区间所有的端点进行排序） 
		memset(dp, 0, sizeof dp); //dp数组清零 
		ll maxl=0; //初始最大值 
		for (int i=1; i<=2*k; i++) {
			if (b[i].f==0) //判断当前点的标记是0还是1,0表示起始点，1则表示终点 
				dp[b[i].id]=maxl+b[i].len; //若是起始点，则更新到当这段的最大长度
			else
				maxl=max(maxl, dp[b[i].id]); //若是终点，则更新最大值
		}
		ll ans=0;
		for (int i=1; i<=k; i++)
			ans=max(ans, dp[i]); //比较最大值 
		printf("%lld\n", ans); //输出 
	}
	return 0;
}
/*
区间贪心+离散化DP
*/