程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 3704(昊昊的機油之GRST-維護構造貪心解)

BZOJ 3704(昊昊的機油之GRST-維護構造貪心解)

編輯:C++入門知識

BZOJ 3704(昊昊的機油之GRST-維護構造貪心解)


3704: 昊昊的機油之GRST

Time Limit: 10 Sec Memory Limit: 1024 MB
Submit: 47 Solved: 15
[Submit][Status]

Description

昊昊有個好機油,他就是傳說中的著力點。現在昊昊獲得了一份長度為n的GRST牌(mod 4 意義下),打算作為送給好機油的生日礼物(不是在2月的麼)。但是,昊昊深知他的機油是個神犇,作為數字控的他,只會喜歡特定的序列。但是昊昊不怕,他可以使用一次菲亞特(他的機油最喜歡的大招),將一段區間內的數字全部+1,若某個數字為3,則+1後變為0。但昊昊的神力是有限的,問從初始序列a到達最終序列b,最少需要使用多少次菲亞特。

Input

第一行一個正整數n,表示GRST長度。
接下來兩行,每行n個值,分別表示ai bi。

Output

僅一個數,即最少需要使用多少次菲亞特。

Sample Input

3
0 2 1
1 0 2

Sample Output

2

HINT

數據規模與約定

樣例說明:第一次對區間[1,2] 使用菲亞特。第二次對區間[2,3] 使用菲亞特。N<=10000000 , 0<=ai,bi<=3





Source


每個單位要按的次數%4 是確定的 記為c1.

如果我們只能對[a,n]進行操作,那麼每段高度就是確定且單調增的 記為c

將其拆分為d ,則d∈{0,1,2,3}

考慮,序列 ci,ci+3,c[i+2] 。。單調增。。。cn , 此時ans=cn

若改為 ci,ci-1,c[i+2]-4...cn-4 此時ans'=ans-3 ([c[i+1],n]減少4,但是多了[ci,ci])

先後對多3,多2,多1情況分析,得到維護後的貪心解。


#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (4)
#define MAXN (10000000+10)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
int sub(int a,int b){return (a-b+(a-b)/F*F+F)%F;}

typedef long long ll;
int n,a[MAXN],b[MAXN],c[MAXN],d[MAXN],f[MAXN]; //序列a,b 第i格維護的次數c,c的拆分序列d,f為c的高度/4 
int decrease(int h) //h:若c序列中 有 p,p+h  則維護成 p,p+h-4 減少的魔法次數為 
{
	int dec_time=0;
	For(i,n) 
		if (dec_timec[i]) c[i]+=4;
		d[i]=c[i]-c[i-1];
		f[i]=c[i]/4;
	}
//	For(i,n) cout<








  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved