キャンディ分割(ダイナミックプランニング)
2253 ワード
问题详述:n个人分糖を与えると仮定し、n个人が持つ糖の数の初期値はA[0]、A[1]、...A[n-1].今、このn人に砂糖を分けます.砂糖を分けるたびに、次の3つのルールの1つに従います.
(1)選択した一人を除いて、他のすべての人に砂糖を1粒与える.
(2)選択した一人を除いて、他のすべての人に砂糖を2粒与える.
(3)選択した1人を除いて、他のすべての人に5粒の砂糖を与える.
問:少なくとも何回砂糖を分けてこのn人のキャンディの数を同じにすることができます
分析:MinでA配列の最小値を記録するには、c[i]でi番目の人を選択してもよい.d[i]は、このc[i]でi番目の人が分けていないキャンディの総数を表し、任意のi,jに対して、d[i]-d[j]=A[i]-A[j]があり、すなわち、i番目の人とj番目の人が分けていない糖果数の差は彼らの初値と同じである.たとえば
A: 1 ,5 ,5
方法1:
1回目はA[1]を選定し、A[0]、A[1]にそれぞれ5粒の糖を分け、現在A:6、5、10;2回目はA[0]を選定し、A[1]、A[2]に砂糖を1粒分け、現在A:6、6、11;3回目にA[2]を選定し、A[0]、A[1]に5粒の糖を与え、最後に11粒の糖を与えた.割当てが完了し、割当て回数は3です.ここで、A[0],A[1],A[2]はそれぞれ1回選択されている.すなわち、c[0]=c[1]=c[2]=1である.d[0]=1,d[1]=5,d[2]=5,彼の差は初期値の差と同じである
方式2:
1、2回目はA[1]を選定し、毎回A[0]を投与し、A[2]はそれぞれ2粒の糖を分け、分けた後Aはそれぞれ3、5、7であった. 5, 5, 9 .
3、4回目にA[2]を選定し、毎回A[0]を投与し、A[1]はそれぞれ2粒の糖を分け、分けた後Aはそれぞれ7、7、9であった. 9, 9, 9 .
合計4回に分けて、c[0]=0、c[1]=2、c[2]=2;d[0]=0,d[1]=4,d[2]=4.
k回の割り当て後にジョブが完了すると仮定すると、k=step(d[0])+step(d[1])+...+step(d[n-1]); ここでstep(n)はn粒のキャンディを分けるのに必要な最小回数を表し、step(n)=n/5+n%5/2+n%5%2である.
注意step(n)>=step(n+1)、step(n+2)、step(n+3)、step(n+4)、例えばstep(9)=4>step(10)=2があるかもしれませんが、必ずstep(n)があります
必ずしもそうとは限らない.先ほどの分析のように、d[m]=0はstep(d[m])が0が最小であることを保証できるが、step(d[i])が最小であることを保証することはできない.原因は何ですか.方式1ではd[0]=1,d[1]=5,d[2]=5のそれぞれが方式2のd[0]=0,d[1]=4,d[2]=4よりも大きいがstep(4)=2,step(5)=1であるため,問題はここにある.だから私たちは最小kを探す時、d[m]=0,1,2,3,4に対して求めたkに対して最小値を取って、このように得た結果こそ本当の最小です.
プログラム中のdp[i]はstep(i)である.
(1)選択した一人を除いて、他のすべての人に砂糖を1粒与える.
(2)選択した一人を除いて、他のすべての人に砂糖を2粒与える.
(3)選択した1人を除いて、他のすべての人に5粒の砂糖を与える.
問:少なくとも何回砂糖を分けてこのn人のキャンディの数を同じにすることができます
分析:MinでA配列の最小値を記録するには、c[i]でi番目の人を選択してもよい.d[i]は、このc[i]でi番目の人が分けていないキャンディの総数を表し、任意のi,jに対して、d[i]-d[j]=A[i]-A[j]があり、すなわち、i番目の人とj番目の人が分けていない糖果数の差は彼らの初値と同じである.たとえば
A: 1 ,5 ,5
方法1:
1回目はA[1]を選定し、A[0]、A[1]にそれぞれ5粒の糖を分け、現在A:6、5、10;2回目はA[0]を選定し、A[1]、A[2]に砂糖を1粒分け、現在A:6、6、11;3回目にA[2]を選定し、A[0]、A[1]に5粒の糖を与え、最後に11粒の糖を与えた.割当てが完了し、割当て回数は3です.ここで、A[0],A[1],A[2]はそれぞれ1回選択されている.すなわち、c[0]=c[1]=c[2]=1である.d[0]=1,d[1]=5,d[2]=5,彼の差は初期値の差と同じである
方式2:
1、2回目はA[1]を選定し、毎回A[0]を投与し、A[2]はそれぞれ2粒の糖を分け、分けた後Aはそれぞれ3、5、7であった. 5, 5, 9 .
3、4回目にA[2]を選定し、毎回A[0]を投与し、A[1]はそれぞれ2粒の糖を分け、分けた後Aはそれぞれ7、7、9であった. 9, 9, 9 .
合計4回に分けて、c[0]=0、c[1]=2、c[2]=2;d[0]=0,d[1]=4,d[2]=4.
k回の割り当て後にジョブが完了すると仮定すると、k=step(d[0])+step(d[1])+...+step(d[n-1]); ここでstep(n)はn粒のキャンディを分けるのに必要な最小回数を表し、step(n)=n/5+n%5/2+n%5%2である.
注意step(n)>=step(n+1)、step(n+2)、step(n+3)、step(n+4)、例えばstep(9)=4>step(10)=2があるかもしれませんが、必ずstep(n)があります
必ずしもそうとは限らない.先ほどの分析のように、d[m]=0はstep(d[m])が0が最小であることを保証できるが、step(d[i])が最小であることを保証することはできない.原因は何ですか.方式1ではd[0]=1,d[1]=5,d[2]=5のそれぞれが方式2のd[0]=0,d[1]=4,d[2]=4よりも大きいがstep(4)=2,step(5)=1であるため,問題はここにある.だから私たちは最小kを探す時、d[m]=0,1,2,3,4に対して求めたkに対して最小値を取って、このように得た結果こそ本当の最小です.
プログラム中のdp[i]はstep(i)である.
#include
#include
#include
#include
using namespace std;
#define _MAX 1000000007
int minStep(int A[],int n)
{
int i=0,Min = _MAX,Max = -1;
while(i=2) dp[i] = min(dp[i],dp[i-2]+1);
if(i>=5) dp[i] = min(dp[i],dp[i-5]+1);
}
int res = _MAX;
for(i=Min;Min-i<5;i--){
int sum=0;
for(int j=0;j