积木大赛:
之前没有仔细地想，然后就直接暴力一点（骗点分），去扫每一高度，连到一起的个数，于是2组超时
先把暴力程序贴上来（可以当对拍机）
#include<iostream>
#include<cstdio>
using namespace std;
FILE *fin = fopen("block.in","r");
FILE *fout= fopen("block.out","w");
int *h;
int n;
int maxHeight = -;
long long times = ;
int main(){
fscanf(fin,"%d",&n);
h = new int[(const int)(n + )];
for(int i = ;i <= n;i++){
fscanf(fin,"%d",&h[i]);
if(h[i] > maxHeight) maxHeight = h[i];
}
char isNew = 0x00;
for(int i = ;i <= maxHeight;i++){
isNew = 0x00;
for(int j = ;j <= n;j++){
if(h[j] >= i && isNew == ){
times++;
isNew = 0x01;
}
if(h[j] < i && isNew== 0x01){
isNew = 0x00;
}
}
}
fprintf(fout,"%ld",times);
}
然而用样例来举个例子
*
* *
* * * *
* * * * *
-----------------------------
当第i列的目标高度比第（i-1）高的时候，很容易发现，需要多耗费（h[i]-h[i - 1]）次操作，因为在操作使第（i-1）列达到目标高度时，第i列和目标高度还差
（h[i]-h[i - 1]）,每次只能放一层的积木，所以需要多耗费（h[i]-h[i - 1]）次操作。
例如把第一层放满，其它层还需要的高度
*
* * *
-----------------------------
这样会很奇怪，为什么第5列还需要放一次呢？那是因为第一次方的区间是[1,5]，每次求差相当于把这一块连续的这一块放上积木
从图中可以看出如果h[i] <= h[i - 1]则不用处理，于是我们可以得到如下递推式
|- f[i - ] ( h[i] <= h[i - 1] )
f[i]=|
|- f[i - ] + ( h[i]-h[i - 1] ) ( h[i] > h[i - 1] )
最后，附上代码，说明长，代码不长:
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("block.in");
ofstream fout("block.out");
int buffer[];
int n;
long long result = ;
int main(){
fin>>n;
for(int i = ;i <= n;i++){
fin>>buffer[];
if( buffer[] > buffer[] ) result += buffer[] - buffer[];
buffer[] = buffer[];
}
fout<<result;
return ;
}
积木大赛
花匠:
这道题最开始用的是DP，虽然没有优化且明知复杂度是O（N2）但还是用它去骗骗分
#include<iostream>
#include<cstdio>
using namespace std;
FILE *fin = fopen("flower.in","r");
FILE *fout= fopen("flower.out","w");
int *f;
int *f1;
int *h;
int n;
int main(){
fscanf(fin,"%d",&n);
f = new int[(const int)(n + )];
f1 = new int[(const int)(n + )];
h = new int[(const int)(n + )];
for(int i = ;i <= n;i++){
fscanf(fin,"%d",&h[i]);
f[i] = ;
f1[i] = ;
}
for(int i = ;i <= n; i++){
for(int j = i-;j > ;j--){
if(f[j]% == &&h[i]>h[j]){
f[i] = max( f[j] + ,f[i]);
}
if(f1[j]% == &&h[i]<h[j]){
f1[i] = max(f1[j] + ,f1[i]);
}
if(f[j]% == &&h[i]<h[j]){
f[i] = max(f[j] + ,f[i]);
}
if(f1[j]% == &&h[i]>h[j]){
f1[i] = max(f1[j] + ,f1[i]);
}
}
}
int maxv = -;
for(int i = ;i <= n;i++){
maxv = max(f[i],maxv);
maxv = max(f1[i],maxv);
}
fprintf(fout,"%ld",maxv);
return ;
}
至于最简单、快捷的方法就是找拐点，一个拐点就是一个答案，至于依据嘛，画画图就能理解了
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("flower.in");
ofstream fout("flower.out");
int n;
int *h;
int result = ;
void init(){
fin>>n;
h = new int[(const int)(n + )];
memset(h, ,sizeof(int)*(n + ));
for(int i = ;i <= n;i++){
fin>>h[i];
}
}
char aFlag = -;
int main(){
init();
for(int i = ;i < n; i++){
if(h[i] > h[i + ] && (aFlag == || aFlag == -) ){
result++;
aFlag = ;
}
if(h[i] < h[i + ] && (aFlag == || aFlag == -) ){
result++;
aFlag = ;
}
}
fout<<result;
return ;
}
花匠-找拐点