yukicoder : No.818 Dinner time

今回参加してたら818も819も苦戦してそう。
https://yukicoder.me/problems/no/818

問題

N匹のニワトリがいて、1～Nの番号が振られている。

M日にわたり、以下の処理を繰り返す。

• 1≦K≦Nである整数Kを選択する。
• 1～K番のニワトリのうち残っているものに対し、個別に卵を産ませるか鶏肉にするか選択させる。
  • その際、ニワトリiに対し前者はスコアA[i]、後者はB[i]を得る。
  • 一旦鶏肉にしたニワトリは以後列から除外する。

総スコアの最大値を求めよ。

解法

中途半端な回数卵を産ませる選択肢はなく、実際は各ニワトリ以下のいずれかしか選択肢の意味はない。

• 1回も選択しない
• 1回だけ選択し、鶏肉にする
• M回とも選択するが、初回鶏肉にする
• M回とも選択し、いずれも卵を産ませる
• M回とも選択し、(M-1)回卵を産ませて最後鶏肉にする

さて、番号の少ないニワトリの選択回数が少ない場合、以後のニワトリの選択回数はそれ以下でなければならない。
ただ、後者3つの選択肢は、「M回とも選択する」という条件のもとでは個々のニワトリについてどれを選択してもよい。
よって、先頭から順にずっとM回選択した場合と、途中から１回だけ選択した場合のスコアの最大値を持ち状態遷移を考えていけばよい。

int N,M;
ll A[101010],B[101010];
ll dp[101010][2];
ll AS,BS;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	ll ma=-1LL<<60;
	
	FOR(i,N) {
		cin>>A[i]>>B[i];
		if(i) dp[i+1][0]=max(dp[i][0],dp[i][1])+max(A[i],B[i]);
		else dp[i+1][0]=-1LL<<60;
		dp[i+1][1]=dp[i][1]+max({B[i],A[i]*(M-1)+B[i],A[i]*M});
		ma=max({ma,dp[i+1][0],dp[i+1][1]});
	}
	cout<<ma<<endl;
}

まとめ

これ本番出てたら解けるかなぁ…。