2019-10-24测试总结
$merge$
题目大意
有
$n(1 \leqslant n \leqslant 300)$ 个只有$1$ 个数字的集合呈环形排列,并集操作$S \bigcup T$ 会产生$|S| * |T|$ 的收益,其中$|S|$ 表示集合$S$ 的元素个数,现在给定这$n$ 个数字,第i个数字为$a_i$ ($1 \leqslant a_i \leqslant 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 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include<cstdio> #include<algorithm> using namespace std; #define file(SSS) freopen(SSS".in","r",stdin),freopen(SSS".out","w",stdout) #define file_close fclose(stdin),fclose(stdout) #define MAXN 605 int n,a[MAXN][MAXN],dp[MAXN][MAXN]; int t[MAXN]; bool e[MAXN][MAXN][MAXN >> 1]; int main() { file("merge"); scanf("%d",&n); for(int i = 1;i <= n;i ++) { scanf("%d",&t[i]),t[i + n] = t[i]; a[i][i] = 1,a[i + n][i + n] = 1,e[i + n][i + n][t[i]] = 1; } for(int len = 1;len < n;len ++) for(int i = 1;i <= 2 * n - 1 - len;i ++) for(int k = i;k <= i + len;k ++) if(!e[i][i + len][t[k]]) e[i][i + len][t[k]] = 1,a[i][i + len] ++; for(int len = 1;len < n;len ++) for(int i = 1;i <= 2 * n - 1 - len;i ++) for(int k = i;k < i + len;k ++) dp[i][i + len] = max(dp[i][i + len], dp[i][k] + dp[k + 1][i + len] + a[i][k] * a[k + 1][i + len]); int Max = 0; for(int i = 1;i < n;i ++) if(dp[i][i + n - 1] > Max) Max = dp[i][i + n - 1]; printf("%d",Max); file_close; return 0; } |
$climb$
题目大意
有
$n(n \leqslant 10^5)$ 个操作,目标高度$L$ ,第$i$ 个操作可以使高度升高$a_i$ ,并在升高后下降$b_i$ ,每次操作最多使用$1$ 次,同时每次操作之后的高度都不能低于$\sum\limits_{j = 1}^{i} c_j$ ,$a_i,b_i,c_i$ 满足$0 \leqslant a_i,b_i,c_i \leqslant 10^9$ ,任何时候,当高度满足高度$h >= L$ 时,操作结束,求最少操作数
贪心思路
首先先看当前高度下最大的
否则看当前高度
贪心的正确性
我们主要是考虑在选定了最大的
然后发现在找贪心的正确性的时候发现了贪心的错误
Hack数据
1 2 3 4 5 6 7 | 3 10 5 2 7 3 1 1 1 1 1 |
显然原来的选择策略变成了错误的
然后就发现标程从300
被卡成了290
还是放一下考场上的代码:
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include<cstdio> #include<queue> using namespace std; #define file(SSS) freopen(SSS".in","r",stdin),freopen(SSS".out","w",stdout) #define file_close fclose(stdin),fclose(stdout) #define MAXN 100005 int n,l; struct MED1 { int a,b,r,num; bool operator < (const MED1 &c) const { if(r == c.r) return a > c.a; else return r < c.r; } }m1[MAXN]; struct MED2 { int a,num; bool operator < (const MED2 &c) const {return a < c.a;} }m2[MAXN]; bool vis[MAXN]; int sum[MAXN]; priority_queue<MED1> p; priority_queue<MED2> q; int main() { file("climb"); scanf("%d%d",&n,&l); for(int i = 1;i <= n;i ++) { scanf("%d%d",&m1[i].a,&m1[i].b); m1[i].r = m1[i].a - m1[i].b,m1[i].num = i; m2[i].a = m1[i].a,m2[i].num = i; p.push(m1[i]),q.push(m2[i]); } for(int i = 1;i <= n;i ++) { int x;scanf("%d",&x); sum[i] = sum[i - 1] + x; } int h = 0,cnt = 0; bool flag = 0; while(h < l) { MED2 temp = q.top(); while(vis[temp.num] && !q.empty()) q.pop(),temp = q.top(); if(q.empty()){flag = 1;break;} if(h + temp.a >= l){cnt ++;break;} MED1 TEMP = p.top(); while(vis[TEMP.num]) p.pop(),TEMP = p.top(); vis[TEMP.num] = 1; h += TEMP.r; if(h <= sum[++cnt]){flag = 1;break;} } if(!flag) printf("%d",cnt); else puts("-1"); file_close; return 0; } |
$coin$
高级博弈论,不会