[POI2013]BAJ-Bytecomputer
题目描述
A sequence of integers from the set is given.
The bytecomputer is a device that allows the following operation on the sequence:
incrementing by for any .
There is no limit on the range of integers the bytecomputer can store, i.e., each can (in principle) have arbitrarily small or large value.
Program the bytecomputer so that it transforms the input sequence into a non-decreasing sequence (i.e., such that ) with the minimum number of operations.
给一个只包含-1,0,1的数列,每次操作可以让a[i]+=a[i-1],求最少操作次数使得序列单调不降
输入输出格式
输入格式:
The first line of the standard input holds a single integer (), the number of elements in the (bytecomputer's) input sequence.
The second line contains integers () that are the successive elements of the (bytecomputer's) input sequence, separated by single spaces.
In tests worth 24% of the total points it holds that , and in tests worth 48% of the total points it holds that .
输出格式:
The first and only line of the standard output should give one integer, the minimum number of operations the bytecomputer has to perform to make its input sequence non-decreasing, of the single word BRAK (Polish for none) if obtaining such a sequence is impossible.
Solution
DP。
比较明显的是我们最多也只需要把一个数位加到1,最少减到-1就可以了。用$f[i][j],i\in Z,1\le i \le n,j\in Z,0 \le j \le 2 $表示第i个数的第j状态需要怎么转移过来,然后暴力枚举之前的可能情况,然后直接根据当前的情况进行转移就可以了。
Code
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(arr) memset(arr, 0, sizeof(arr))
const int inf = 0x3f3f3f3f;
int f[1000001][3],n,m,a[1000001],ans;
inline int read()
{
int x=0,c=1;
char ch=' ';
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
while(ch=='-') c*=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
return x*c;
}
int main()
{
//freopen("date.in","r",stdin);
n=read();
memset(f,126,sizeof(f));
for(re int i=1;i<=n;i++)
a[i]=read();
f[1][a[1]+1]=0;
for(re int i=2;i<=n;i++){
if(a[i]==-1){
f[i][0]=f[i-1][0];
f[i][2]=f[i-1][2]+2;
}else if(a[i]==0){
f[i][0]=f[i-1][0]+1;
f[i][1]=min(f[i-1][0],f[i-1][1]);
f[i][2]=f[i-1][2]+1;
}else{
f[i][0]=f[i-1][0]+2;
f[i][1]=f[i-1][0]+1;
f[i][2]=min(min(f[i-1][0],f[i-1][1]),f[i-1][2]);
}
}
ans=min(min(f[n][0],f[n][1]),f[n][2]);
if(ans>200000000) cout<<"BRAK";
else cout<<ans;
return 0;
}
最新文章
- Linux标准输入输出
- js 图片加载完后的处理事件
- js table的笔记,实现添加 td,实现搜索功能
- apache 访问出现403 Forbidden
- 记一次小团队Git实践(下)
- log4net Tutorial
- RedGate .NET Reflector注册问题(反注册)
- 《精通javascript》几个简单的函数
- linux系统中rsync+inotify实现服务器之间文件实时同步
- Check Box Select/Deselect All on Grid
- jquery里的宽度详解
- http权威指南 telnet
- jquery的attr禁用表单元素的方法
- 微服务架构:Eureka参数配置项详解
- MyBatis模糊查询不报错但查不出数据的一种解决方案
- Visual Studio Ultimate 2013
- kafka配置简要描述
- 解读Secondary NameNode的功能
- bp算法中为什么会产生梯度消失?
- yii2增删改查及AR的理解