NOIP2018提高组模拟题(四)

能量(energy)

Description

​ 有一块能量田,它的形状是 n*m的矩形,每一个格子上都有一个能量值 a[x][y] (可正可负)。一块矩形田的能量定义为它的每个格子的能量值之和。

​ 现在,亮亮需要选择一块正方形的能量田,用它的能量来为自己的魔法棒充 值。他当然希望所选择的能量田所含的能量最大,请你帮助他求出这个最大值。

​ 数据保证能量田中至少有一个格子的能量值非负。

Input

一行两个整数 n 和 m。

接下来 n 行,每行 m 个整数。

Output

输出只有一个整数,表示最大的能量。

数据范围,\(1\leq n,m \leq 200\)

明显\(n^3\)可做.

二维前缀和切了!用时6min

不过貌似很多人都挂了?

PS:初值不要赋成0,对起始的每个格子的值取\(max\)

然后枚举正方形边长.

根据二维前缀和的容斥即可.

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define R register using namespace std; inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
} int n,m,res[208][208],ans; signed main()
{
freopen("energy.in","r",stdin);
freopen("energy.out","w",stdout); in(n),in(m);
for(R int i=1;i<=n;i++)
for(R int j=1,x;j<=m;j++)
{
in(x);
res[i][j]=res[i-1][j]+res[i][j-1]-res[i-1][j-1]+x;
ans=max(ans,x);
} R int lim=min(n,m);
for(R int len=2;len<=lim;len++)
for(R int i=1;i<=n-len+1;i++)
for(R int j=1;j<=m-len+1;j++)
{
R int tmp=res[i+len-1][j+len-1];
tmp-=res[i+len-1][j-1];
tmp-=res[i-1][j+len-1];
tmp+=res[i-1][j-1];
ans=max(ans,tmp);
} printf("%lld\n",ans); fclose(stdin);
fclose(stdout); return 0;
}

摘桃(peach)

Description

​ 小林家的桃园里一共有 n 棵桃树,且第 i 棵桃树结有 A[i]个桃子。到了桃子 成熟的季节,如果不及时摘下来,就会从树上掉下来,一旦掉到了地上,桃子就 会因碰撞致坏而无法出售。

​ 小林知道这个消息后,连忙带上了工具,准备去采摘桃子。小林每一天都可 以选择任意一棵桃树,将其上的桃子全部采摘下来。而每一天结束时,第 i 株桃 树会落下 d[i]个桃子(落到一个不剩为止),这些落下的桃子就会因摔坏而被浪 费掉。(注意,对于每一天,小林先采摘桃子,然后一天结束,接下来桃树落桃 子。) 小林一共有 k 天的时间,在这 k 天内,他最多能采摘多少个桃子呢?

Input

第一行有两个整数 n 和 k。

第二行 n 个整数 A[i]表示每株桃树一开始结的桃子数量。

第三行 n 个整数 d[i]表示每株桃树在每天结束时会落下的桃子数量。

Output

一个整数,即小林能采摘的最多的桃子数量 。

这题做过,切!

做法:贪心+DP

很显然,我们优先考虑摘每天掉落的多的桃子.

(防止后面没办法接)

所以贪心地对其掉落的数量进行排序.

设\(DP\)状态

\(f[i][j]\)代表第\(j\)天处理到第\(i\)棵树的最多桃子数量.

考虑状态转移.

  1. 摘桃子
  2. 不摘桃子

\[f[i][j]=max(f[i-1][j],f[i-1][j-1]+now)
\]

这个\(now\)就是当前剩下的.

还有需要注意的是,如果掉没了,我们就不摘,要等于\(0\)。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#define R register using namespace std; const int gz=1008; inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
} int n,k,f[gz][gz],ans; struct cod{int a,d;}tree[gz]; inline bool ccp(const cod&a,const cod&b)
{
return a.d>b.d;
} int main()
{
freopen("peach.in","r",stdin);
freopen("peach.out","w",stdout); in(n),in(k); for(R int i=1;i<=n;i++)in(tree[i].a); for(R int i=1;i<=n;i++)in(tree[i].d); sort(tree+1,tree+n+1,ccp); for(R int j=1;j<=k;j++)
for(R int i=1;i<=n;i++)
{
R int now=tree[i].a-(j-1)*tree[i].d;
if(now<0)now=0;
f[i][j]=max(f[i-1][j],f[i-1][j-1]+now);
} for(R int i=1;i<=k;i++)ans=max(f[n][i],ans); printf("%d\n",ans); fclose(stdin);
fclose(stdout); return 0;
}

魔法通道(road)

Description

​ 亮亮在一条魔法线上按 1,2,3...n 的顺序依次建立了 n 个魔法点,每个魔法点 有两个属性, Si 表示位置, Ii 表示魔力值。对于两个点 i 和 j(i < j),若满足 |Si-Sj|<=(Ii+Ij),则亮亮可以花费(j-i)^2 的魔法值建立一条从 i 到 j 的魔法通道。

​ 现在,有一个小精灵正处于 1 号魔法点,她想要通过魔法通道到达 n 号点, 亮亮希望能用最少的魔法值来帮助她。请你帮亮亮计算一下,他最少需要消耗多少魔法值。

Input

第一行有一个整数 n,表示一共有 n 个魔法点。

接下来 n 行,每行有两个整数 Si 和 Ii,含义如上所述。

Output

一个整数,表示最少消耗的魔法值。

若小精灵无论如何也到达不了 n 号魔法点,则输出-1。

这题对我来说不可做啊.

我们的做法可以\(get\)到\(70pts\)

前部分60分,可以暴力\(DP\) \(O(n^2)\)

然后最后10分,可以特判\(-1\).

\(f[i]\)代表到处理到\(i\)的最小魔法值.

转移方程为

\[f[i]=min(f[i],f[j]+(j-i)^2) \ \ \ \ \ \ \ j\in[1,i)
\]

这应该不是很难理解,就不多解释了.

这里有一个小优化.倒叙枚举\(j\),再判断

\[if((i-j)^2>=f[i])\ break
\]

可以多得30pts。

因为我们的\((j-i)^2\)如果比\(f[i]\)都要大,再加上\(f[j]\)就没有必要去更新\(f[i]\)了.

这样为什么是可行的?

因为我们从左向右处理,\(f[j]\)已经被处理过,如果能够更新,就已经更新了我们的答案.

而\(f[i]\)是极大值的话(未被更新),不会被\((i-j)^2\)影响,所以\(f[i]\)是一定会被某个位置更新的。

这样可以get到很多分.

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#define int long long
#define R register using namespace std; const int gz=300008; inline void in(R int &x)
{
R int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
} int n,f[gz];
struct cod{int s,l;}magic[gz]; inline bool ok(R int i,R int j)
{
return (abs(magic[i].s-magic[j].s))<=(magic[i].l+magic[j].l);
} inline void init()
{
for(R int i=1;i<=n;i++)in(magic[i].s),in(magic[i].l);
} signed main()
{
freopen("road.in","r",stdin);
freopen("road.out","w",stdout); in(n);
init();
for(R int i=2;i<=n;i++)f[i]=21474836476666LL;
f[1]=f[0]=0;
if(n<=233333)
{
for(R int i=1;i<=n;i++)
for(R int j=i-1;j>=1;j--)
{
if(ok(i,j))
f[i]=min(f[i],f[j]+(j-i)*(j-i));
if((j-i)*(j-i)>=f[i])break;
}
printf("%lld",f[n]>=21474836476666LL ? -1:f[n]);
} else
{
for(R int i=1;i<=n;i++)
for(R int j=i-1;j>=1;j--)
if(ok(i,j))
{
f[i]=min(f[i],f[j]+(j-i)*(j-i));
break;
}
printf("%lld",f[n]>=21474836476666LL ? -1:f[n]);
}
fclose(stdin);
fclose(stdout); return 0;
}

T3\(\color{red}{官方题解}\)

考察算法: 区间交、 set、 动规

|Si-Sj|≤Ii+Ij 等价于[Si-Ii,Si+Ii]与[Sj-Ij,Sj+Ij]有交。

在 Si,Ii ∈ Z 的 前 提 下 : [Si-Ii,Si+Ii] 与 [Sj-Ij,Sj+Ij] 有 交 等 价 于(Si-Ii,Si+Ii+1)与 (Sj-Ij,Sj+Ij+1)有交。 将每个整点 x 表示成(x,x+1)。

我们按照编号顺序处理各个区间, 最初, set中有三个 Range:

(-∞,S1-I1) Id=0

P1 Id=1

(S1+I1+1,+∞) Id=0

且 dp[1]=0, dp[0]=+∞。

每次, 首先检查 Pi 的两端点, 是否是 set中各 Range 的分界点, 若否, 该端 点 a 必定属于某区间(u,v),Id=x。 从 a 将该区间分裂成(u,a),Id=x 和(a,v),Id=x。

接下来 Pi 恰等于 set中连续的一段 Range 之和(如果只考虑非整点的话) , 枚举这些 Range, 这些 Range 就是可以“无遮拦” 地看到的 Range, 暴力地从这些 Range 对应的 Id 进行转移, 计算得出 dp[i]。

接下来, Pi 的加入将会遮住这些 Range, 在 i 更大时这些 Range 就不可能被“无遮拦” 地看到了。 从 set中 erase 去这些 Range, 用 Pi 代替。

重复这个过程直至 i=N。 输出 dp[N]。

我们发现一旦一个 Range 被用来转移, 它马上会被 erase。 从而, 一个 Range 最多只 会对应一次转移。 所以, 转移的次数≤进入 set 的 Range 数。

进入 set 有两种情况, 也就是循环开始时的分裂区间(每轮 2 次, 每次净增加 1 个区 间) , 和循环末尾的插入 Pi(每轮 1 次, 每次净增加 1 个区间) 。 从而进入 set 的 Range 数是 O(N)级别的, 约等于 3N。

又易证 set 中每一时刻的元素数都≤2N+1, 从而每次转移的复杂度为 O(logN)。 总复杂度为 O(NlogN), 且实现简便, 常数较小。

上一篇:JSON和GSON操作json数据


下一篇:iOS AVCaptureSession 小视频开发总结,支持设备旋转