一、快餐問題
1.問題引入
Peter最近在R市開了一家快餐店，為了招攬顧客，該快餐店準備推出一種套餐，該套餐由A個漢堡，B個薯條和C個飲料組成。為了提高産量，Peter從著名的麥當勞公司引進了N條生産線。所有的生産線都可以生産漢堡，薯條和飲料，由于每條生産線每天所能提供的生産時間是有限的、不同的，而漢堡，薯條和飲料的機關生産時間又不同。這使得Peter很為難，不知道如何安排生産才能使一天中生産的套餐産量最大。請你編一程式，計算一天中套餐的最大生産量。為簡單起見，假設漢堡、薯條和飲料的日産量不超過100個。
輸入：
輸入檔案共四行。第一行為三個不超過100的正整數A、B、C中間以一個空格分開。第三行為3個不超過100的正整數p1,p2,p3分别為漢堡，薯條和飲料的機關生産耗時。中間以一個空格分開。第三行為N(0<=0<=10)，第四行為N個不超過10000的正整數，分别為各條生産流水線每天提供的生産時間，中間以一個空格分開。
2.思路分析
F[i,j]表示前i條生産線生産j個漢堡,k個薯條所能生産的最多飲料, 則最多套餐ans:=min{j div a,k div b,f[I,j,k] div c}
F[i,j,k]:=max{f[i-1,j',k']+(T[i]-(j-j')*p1-(k-k')*p2) div p3}
時間複雜度 O(10*100^4)
3.代碼如下
二、過河
1.問題引入
在河上有一座獨木橋，一隻青蛙想沿着獨木橋從河的一側跳到另一側。在橋上有一些石子，青蛙很讨厭踩在這些石子上。由于橋的長度和青蛙一次跳過的距離都是正整數，我們可以把獨木橋上青蛙可能到達的點看成數軸上的一串整點：0，1，……，L（其中L是橋的長度）。坐标為0的點表示橋的起點，坐标為L的點表示橋的終點。青蛙從橋的起點開始，不停的向終點方向跳躍。一次跳躍的距離是S到T之間的任意正整數（包括S,T）。當青蛙跳到或跳過坐标為L的點時，就算青蛙已經跳出了獨木橋。
題目給出獨木橋的長度L，青蛙跳躍的距離範圍S,T，橋上石子的位置。你的任務是确定青蛙要想過河，最少需要踩到的石子數。
對于30%的資料，L <= 10000；
對于全部的資料，L <= 10^9。
輸入 輸入的第一行有一個正整數L（1 <= L <= 10^9），表示獨木橋的長度。第二行有三個正整數S，T，M，分别表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個數，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M個不同的正整數分别表示這M個石子在數軸上的位置（資料保證橋的起點和終點處沒有石子）。所有相鄰的整數之間用一個空格隔開。 輸出 輸出隻包括一個整數，表示青蛙過河最少需要踩到的石子數。 樣例輸入
10
2 3 5
2 3 5 6 7
樣例輸出
2
2.思路分析
本來這道題可以說是一道簡單的DP題,狀态轉移方程也容易找出：f [ i ] = min ( f [ i - j ] ) + stone [ i ] S <= j <=T && i >= j
但是,這道題的難點就是獨木橋的長度 L 最高可達到 10^9.如果用正常方法用 for 循環從1遞推到 L + T,難免會逾時.
這個時候我們要用離散化思想來壓縮路徑.
我們會發現：
① f [ i ] 隻跟 f [ (i - j)min ]~ f [ (i - j)max ] ( S <= j <= T && i >= j)有關.
② 石頭的個數M遠遠小于L.換句話意思就是在某兩個石頭之間存在一大段空白,這個時候 f [ i ] 在這個區域遞推值都是不變的.
由于上面的①和②我們可知在遞推 f [ step ] 的時候,我們最多需要f [ step - T ]~ f [ step - S ]之間的值.這個時候我們隻要第一次推出某一個 step1 位置，使得：
f [ step1 - T ]~ f [ step1 - S ] 與 f [ step - T ]~ f [ step - S ] 每個值對應相等.(如果S≠T, f [ step1 - T ]~ f [ step1 - S ] 每個值也是相等的)
剩下的從 step1 到 step就不用遞推了.這裡我們就達到了優化的左右,路徑長度從 step 優化到 step1.
現在我們隻需要找到最大的 step1,然後就可以把 L 壓縮到 step1*M.
若 p*x+(p+1)*y=Q（采用跳躍距離 p 和 p+1 時可以跳至任何位置 Q），則在Q ≥ P*（P-1）時是一定有解的。
由于題目給出的一個區間是1≤S≤T≤10，于是當相鄰的兩個石子之間的距離不小于8*9=72時，則後面的距離都可以到達，我們就可以認為它們之間的距離就是72。如此一來，我們就将原題L的範圍縮小為了100*72=7200，動态規劃算法完全可以承受了。
特殊的,S=T的時候,那麼上式方程無恒解,而f [ step1 - T ]~ f [ step1 - S ] 之間的每個值并不是都想等的，但 f [ step1 - T ]~ f [ step1 - S ] 與 f [ step - T ]~ f [ step - S ] 每個值對應相等.是以對于這種情況我們不能簡簡單單的把兩個石頭之間的距離壓縮成72.而是還要加上除以72的餘數.
壓縮政策： 那麼對于每兩個石頭之間的距離 Xi.
① 當Xi＜2*72的時候，不予壓縮.
②當Xi≥2*72的時候，壓縮Xi=72-(Xi)%72 ;
總規模最大為：2*100*72=14400.
3.代碼如下
<span style="color:#330099">package 動态規劃__貪心的動态規劃;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class 過河 {
static int L, s, t, m;
static int a[]=new int[111];
static int f[]=new int[210111];
static int dp[]=new int[210111];
public static void main(String args[]) throws IOException{
BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
String x=buf.readLine();
L=Integer.parseInt(x);
String y=buf.readLine();
String y1[]=y.split(" ");
s=Integer.parseInt(y1[0]);
t=Integer.parseInt(y1[1]);
m=Integer.parseInt(y1[2]);
String z=buf.readLine();
String z1[]=z.split(" ");
for(int i = 1; i <= m; i++)
a[i]=Integer.parseInt(z1[i-1]);
Arrays.sort(a);
a[0] = 0;
int tmp = t;
int pos = 0;
for(int i = 1; i <= m; i++)
{
int d = a[i] - a[i - 1];
if(d > 2 * tmp)
{
if(d % tmp == 0) d = tmp;
else d = d % tmp;
d += tmp;
}
pos = pos + d;
f[pos] = 1;
}
dp[0] = 0;
for(int i = 1; i <= 22222; i++) dp[i] = 1000;
int mi;
for(int i = 1; i <= pos + t; i++)
{
mi = 1000;
for(int j = i - t; j <= i - s; j++)
if(j >= 0 && dp[j] < mi)
mi = dp[j];
dp[i] = mi + f[i];
}
mi = 1000;
for (int i = pos + 1; i <= pos + t; i++)
if (dp[i] < mi)
mi = dp[i];
System.out.print(mi);
}
}</span>
![Java排序算法---快速排序[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)