【SDOI 2009】学校の食堂Dining
3972 ワード
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1226
[SDOI 2009]学校食堂Dining
Time Limit：1000 MS メモリLimit：265536 KTotal Submit：62 Acceepted：34 Case Time Limit：1000 MS
Description
Fさんの学校は都市の片隅にあります。すべての学生は学校で食事をします。学校には食堂があります。粗末ですが、食堂のシェフはいつもクラスメートに満足させる料理を作っています。もちろん、人によって味が違うとは限らないですが、一人一人の好みは全部マイナスではない数字で表してもいいです。人手が足りないので、食堂では毎回一人分の料理しかできません。各料理を作るのに必要な時間は前の料理と関係があります。前の料理の対応する味がaであれば、この料理はbで、この料理を作るのに必要な時間は（a or b）-（a and b）で、最初の料理を作るのに時間はかかりません。ここで、orとandは整数単位または演算およびビット単位と演算を表し、C言語で対応する演算子は「|」および「&」である。学生の数はこの学校より多いです。食事や料理に時間がかかります。そのため、学校の食堂では、みんなの順番に料理をしないで、総食事の時間を短縮します。学生たちは学校の食堂のこのようなやり方を理解することができますが、各学生はやはりある程度の許容度があります。つまり、チームの中のi番目のクラスメートは、一番多く彼の後に付いているBi個人が先に食事を取ることが許されます。この後の任意の学生が今のクラスメートより先に食事を取ったら、今の学生は非常に怒ります。だから、食堂で料理をします。クラスメートの気持ちを配慮しなければなりません。今、Fさんはすべての人の許容度を満たすという前提の下で、自分の学校の食堂でこれらの料理を作るには、少なくともどれぐらいの時間がかかりますか？
Input
最初の行は正の整数Cを含み、テストポイントのデータ群数を表します。各グループのデータの最初の行は正の整数Nを含み、級数を表します。各グループのデータの第二行からN行を共有し、各行はスペースで区切られたマイナスの整数TiとBiを含み、列順に後の各学生に必要な料理の味とこの学生の忍耐度を表しています。各グループのデータの間に空行がない。
Output
C行を含み、各行の整数は、対応データの中で食堂がすべての料理を完成するのに必要な最小時間を表しています。
Sample Input
第一グループのデータについて：クラスメート1はクラスメート2またはクラスメート3が彼の前に料理を取ることができます。クラスメート2はクラスメート3が彼の前に料理を取ってもいいです。クラスメート3はけちで、彼は後ろのクラスメートより先に料理を持ってきなければなりません。一番いい案はクラスメート3、クラスメート2、クラスメート1、クラスメート4、クラスメート5によって料理を作ります。各料理に必要な時間は0、8、1、6及び1です。【データ規模と約束】30%のデータに対して、1≦N≦20を満足する。100%のデータについては、1≦N≦1,000,0≦Ti≦1,000,0≦Bi≦7,1≦C≦5を満足する。30%のデータがあり、0≦Bi≦1を満たす。65%のデータがあり、0≦Bi≦5を満たす。45%のデータがあり、0≦Ti≦130を満たす。
最近本当に状態に圧縮されて暴発しました。
Bi<=7を見たら、形にdpを押して考えます。この問題は私にとってかなり難しいです。了解問題の報告書を見て、書き終わってからまた長い間経ってACが落ちました。
書いたのは問題があるかもしれません。理解してください。
まず、（a or b）-（a and b）=a xor bを明確にします。なぜですか？自分で考えてみます。
私達はi番目の人が並んでいる時、彼が一番多くて七人の彼の後ろの人が彼より先に料理を持ってくるのを我慢できると知っています。
f[i，j，k]はi番目の人が全部料理を持ってくることを表しています。彼の後にまだ料理を取っていない人の集まりj{…}は、前の人がkの最小時間です。kの表現については、1.nを使用して表現する必要はなく、iに対する位置座標だけを記録すればいいです。例えば、k=1、つまりkはiの後ろの第一人者で、k=-2はiの前の第2人を表します。このようにして、kの状態は[-8..7]で表現できる。
そして列挙状態。ある状態f[i，j，k]において、iの後の一人が料理を取った場合、状態f[i，j，k]はf[i＋1,(j>>1)or(1<<7)、k-1)に伝達されます。そうでなければ、合法的なLを列挙して最適値を計算する必要があります。
[SDOI 2009]学校食堂Dining
Time Limit：1000 MS メモリLimit：265536 KTotal Submit：62 Acceepted：34 Case Time Limit：1000 MS
Description
Fさんの学校は都市の片隅にあります。すべての学生は学校で食事をします。学校には食堂があります。粗末ですが、食堂のシェフはいつもクラスメートに満足させる料理を作っています。もちろん、人によって味が違うとは限らないですが、一人一人の好みは全部マイナスではない数字で表してもいいです。人手が足りないので、食堂では毎回一人分の料理しかできません。各料理を作るのに必要な時間は前の料理と関係があります。前の料理の対応する味がaであれば、この料理はbで、この料理を作るのに必要な時間は（a or b）-（a and b）で、最初の料理を作るのに時間はかかりません。ここで、orとandは整数単位または演算およびビット単位と演算を表し、C言語で対応する演算子は「|」および「&」である。学生の数はこの学校より多いです。食事や料理に時間がかかります。そのため、学校の食堂では、みんなの順番に料理をしないで、総食事の時間を短縮します。学生たちは学校の食堂のこのようなやり方を理解することができますが、各学生はやはりある程度の許容度があります。つまり、チームの中のi番目のクラスメートは、一番多く彼の後に付いているBi個人が先に食事を取ることが許されます。この後の任意の学生が今のクラスメートより先に食事を取ったら、今の学生は非常に怒ります。だから、食堂で料理をします。クラスメートの気持ちを配慮しなければなりません。今、Fさんはすべての人の許容度を満たすという前提の下で、自分の学校の食堂でこれらの料理を作るには、少なくともどれぐらいの時間がかかりますか？
Input
最初の行は正の整数Cを含み、テストポイントのデータ群数を表します。各グループのデータの最初の行は正の整数Nを含み、級数を表します。各グループのデータの第二行からN行を共有し、各行はスペースで区切られたマイナスの整数TiとBiを含み、列順に後の各学生に必要な料理の味とこの学生の忍耐度を表しています。各グループのデータの間に空行がない。
Output
C行を含み、各行の整数は、対応データの中で食堂がすべての料理を完成するのに必要な最小時間を表しています。
Sample Input
2
5
5 2
4 1
12 0
3 3
2 2
2
5 0
4 016
1第一グループのデータについて：クラスメート1はクラスメート2またはクラスメート3が彼の前に料理を取ることができます。クラスメート2はクラスメート3が彼の前に料理を取ってもいいです。クラスメート3はけちで、彼は後ろのクラスメートより先に料理を持ってきなければなりません。一番いい案はクラスメート3、クラスメート2、クラスメート1、クラスメート4、クラスメート5によって料理を作ります。各料理に必要な時間は0、8、1、6及び1です。【データ規模と約束】30%のデータに対して、1≦N≦20を満足する。100%のデータについては、1≦N≦1,000,0≦Ti≦1,000,0≦Bi≦7,1≦C≦5を満足する。30%のデータがあり、0≦Bi≦1を満たす。65%のデータがあり、0≦Bi≦5を満たす。45%のデータがあり、0≦Ti≦130を満たす。
最近本当に状態に圧縮されて暴発しました。
Bi<=7を見たら、形にdpを押して考えます。この問題は私にとってかなり難しいです。了解問題の報告書を見て、書き終わってからまた長い間経ってACが落ちました。
書いたのは問題があるかもしれません。理解してください。
まず、（a or b）-（a and b）=a xor bを明確にします。なぜですか？自分で考えてみます。
私達はi番目の人が並んでいる時、彼が一番多くて七人の彼の後ろの人が彼より先に料理を持ってくるのを我慢できると知っています。
f[i，j，k]はi番目の人が全部料理を持ってくることを表しています。彼の後にまだ料理を取っていない人の集まりj{…}は、前の人がkの最小時間です。kの表現については、1.nを使用して表現する必要はなく、iに対する位置座標だけを記録すればいいです。例えば、k=1、つまりkはiの後ろの第一人者で、k=-2はiの前の第2人を表します。このようにして、kの状態は[-8..7]で表現できる。
そして列挙状態。ある状態f[i，j，k]において、iの後の一人が料理を取った場合、状態f[i，j，k]はf[i＋1,(j>>1)or(1<<7)、k-1)に伝達されます。そうでなければ、合法的なLを列挙して最適値を計算する必要があります。
program SDOI_2009_Dining;
var f:array[0..1001,0..(1 shl 8)-1,-8..7]of longint;
t,b:array[1..1000]of longint;
inf,ans,Max_Anger,n,c,i,j,k,l:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a);
exit(b);
end;
begin
readln(c);
while c>0 do
begin
dec(c);
readln(n);
fillchar(t,sizeof(t),0);
fillchar(b,sizeof(b),0);
fillchar(f,sizeof(f),$7f);
inf:=f[0,0,0];
for i:=1 to n do readln(t[i],b[i]);
f[1,1<<8-1,-1]:=0;
for i:=1 to n do
for j:=(1<<8)-1 downto 0 do
for k:=-8 to 7 do
if f[i,j,k]<inf then
begin
if (j and 1=0)then
f[i+1,(j>>1)or(1<<7),k-1]:=f[i,j,k]
else
begin
Max_Anger:=inf;
for l:=0 to 7 do
if j and (1<<l)<>0 then
begin
if i+l>Max_Anger then break;
Max_Anger:=min(Max_Anger,i+l+b[i+l]);
if i+k<=0 then f[i,j and not(1<<l),l]:=min(f[i,j and not(1<<l),l],0)
else f[i,j and not(1<<l),l]:=min(f[i,j and not(1<<l),l],f[i,j,k]+(t[i+k] xor t[i+l]));
end;
end;
end;
ans:=maxlongint;
for i:=-8 to -1 do
ans:=min(ans,f[n+1,(1<<8)-1,i]);
writeln(ans);
end;
readln;readln;
end.