洛谷P3078 [USACO13MAR]扑克牌型Poker Hands

题目描述

Bessie and her friends are playing a unique version of poker involving a deck with \(N\) (\(1 \leq N \leq 100000\)) different ranks, conveniently numbered \(1..N\) (a normal deck has \(N = 13\)). In this game, there is only one type of hand the cows can play: one may choose a card labeled \(i\) and a card labeled j and play one card of every value from i to \(j\). This type of hand is called a "\(straight\)".

Bessie's hand currently holds \(a_i\) cards of rank \(i (0 \leq a_i \leq 100000\)). Help her find the minimum number of hands she must play to get rid of all her cards.

一个牛有\(N\)堆牌，每堆排数量不等。一只牛一次可以将第\(i\)张到第\(j\)张各打一张出去，问最少几次打完

输入输出格式

输入格式：

Line \(1\): The integer \(N\).

Lines \(2..1\)+\(N\): Line \(i\)+\(1\) contains the value of \(a_i\).

输出格式：

Line \(1\): The minimum number of straights Bessie must play to get rid of all her cards.

输入输出样例

输入样例#1：

输出样例#1：

说明

Bessie can play a straight from \(1\) to \(5\), a straight from \(1\) to \(2\), a straight from \(4\) to \(5\), two straights from \(2\) to \(2\), and a straight from \(5\) to \(5\), for a total of \(6\) rounds necessary to get rid of all her cards.

思路：双倍经验……跟\(noip2018\) \(Day1T1\)一样……本来还以为是线段树，所以才点进来。

代码：

#include<cstdio>

#include<cctype>

#define maxn 100007

#define ll long long

using namespace std;

int n,a[maxn];

ll ans;

inline int qread() {

	char c=getchar();int num=0,f=1;

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) num=num*10+c-'0';

	return num*f;

}

int main() {

	n=qread();

	for(int i=1;i<=n;++i) {

		a[i]=qread();

		if(a[i]>a[i-1]) ans+=a[i]-a[i-1];

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

洛谷P3078 [USACO13MAR]扑克牌型Poker Hands

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章