輾轉相減，新手入門題。兩個容量的灌水題，無所謂最優解。
1 #include<stdio.h>
2
3 int main(){
4 int A,B,T,sA,sB;
5 while(scanf("%d %d %d",&A,&B,&T)>=0){
6 sA=sB=0;
7 while(1){
8 if(sA==0){
9 printf("fill A\n");
10 sA=A;
11 }
12 else{
13 printf("pour A B\n");
14 sB+=sA;
15 if(sB>=B){
16 if(B!=T){
17 printf("empty B\n");
18 sA=sB-B;
19 sB=0;
20 }
21 else
22 sB=B;
23 }
24 else
25 sA=0;
26 }
27 if(sB==T){
28 printf("success\n");
29 break;
30 }
31 }
32 }
33 return 0;
34 }
zju搜索dp題目總結收藏
|
搜索：
50道搜索題
1002 Fire Net -ok
1004 Anagrams by Stack -ok
1005 Jugs -ok
1008 Gnome Tetravex -ok but not ac
1091 Knight Moves -ok
1101 Gamblers -ok
1204 Additive equations
1221 Risk
1230 Legendary Pokemon
1249 Pushing Boxes
1364 Machine Schedule
1368 BOAT
1406 Jungle Roads ---ok
1411 Anniversary
1453 Surround the Trees 凸包
1516 Uncle Tom's Inherited Land ---ok
1525 Air Raid 算網絡流問題可能更合適一點
1586 QS Network
1602 Multiplication Puzzle dp
1649 Rescue
1671 Walking Ant----ok
1711 Sum It Up dfs----ok
1901 A Star not a Tree? 說他搜索可能有點爭議（不管了）
1940 Dungeon Master----ok
2100 Seeding ----ok
2110 Tempter of the Bone
2140 Ball
（27道）
上面的題可能比較簡單，就當練練基本算法吧
===============================================================================
下面的題沒有容易做的。
難題&經典
1003 Crashing Balloon
1015 Fishing Net 完美圖
1144 Robbery
1149 Dividing up
1161 Gone Fishing
1197 Sorting Slides
1217 Eight
1228 Farewell, My Friend
1237 Fans and Gems
1455 Schedule Problem
1456 Minimum Transport Cost 圖論 最短路徑 要保存路徑
1492 Maximum Clique 圖論 經典算法--最大團
1600 Market Place
1605 One-way Traffic
1568 WishingBone's Room Plan
1742 Gap 至今一點想法都沒有，難！！！
1743 Concert Hall Scheduling
1827 The Game of 31 博弈
1855 Maze
1903 Jogging Trails 中國郵路問題
1909 Square 經典的dfs.
2064 Bomberman - Just Search! 經典！
2094 Max Angle 計算幾何+博弈
2125 Rocket Mania
2126 Rocket Mania Plus
2127 Zuma
2128 Seven Seas
2129 Mummy Maze
2142 Light The Square
（24道）
===========================================
dp
50道dp的題
1499 Increasing Sequenc......余下全文>>
能不能把問題貼出來啊？
我做了一道ZOJ1005題，差不多吧
In the movie "Die Hard 3", Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug and were asked to fill the 5-gallon jug with exactly 4 gallons. This problem generalizes that puzzle.
You have two jugs, A and B, and an infinite supply of water. There are three types of actions that you can use: (1) you can fill a jug, (2) you can empty a jug, and (3) you can pour from one jug to the other. Pouring from one jug to the other stops when the first jug is empty or the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A.
A problem is given by a triple (Ca,Cb,N), where Ca and Cb are the capacities of the jugs A and B, respectively, and N is the goal. A solution is a sequence of steps that leaves exactly N gallons in jug B. The possible steps are
fill A
fill B
empty A
empty B
pour A B
pour B A
success
where "pour A B" means "pour the contents of jug A into jug B", and "success" means that the goal has been accomplished.
You may assume that the input you are given does have a solution.
Input
Input to your program consists of a series of input lines each defining one puzzle. Input for each puzzle is a single line of three positive integers: Ca, Cb, and N. Ca and Cb are the capacities of jugs A and B, an......余下全文>>
