Michael likes snowboarding. That’s not very surprising, since snowboarding is really great. The bad thing is that in order to gain speed, the area must slide downwards. Another disadvantage is that when you’ve reached the bottom of the hill you have to walk up again or wait for the ski-lift. Michael would like to know how long the longest run in an area is. That area is given by a grid of numbers, defining the heights at those points. Look at this example: 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 One can slide down from one point to a connected other one if and only if the height decreases. One point is connected to another if it’s at left, at right, above or below it. In the sample map, a possible slide would be 24-17-16-1 (start at 24, end at 1). Of course if you would go 25-24-23-…-3-2-1, it would be a much longer run. In fact, it’s the longest possible. Input The first line contains the number of test cases N. Each test case starts with a line containing the name (it’s a single string), the number of rows R and the number of columns C. After that follow R lines with C numbers each, defining the heights. R and C won’t be bigger than 100, N not bigger than 15 and the heights are always in the range from 0 to 100. Output For each test case, print a line containing the name of the area, a colon, a space and the length of the longest run one can slide down in that area. Sample Input 2 Feldberg 10 5
56 14 51 58 88
26 94 24 39 41
24 16 8 51 51
76 72 77 43 10
38 50 59 84 81
5 23 37 71 77
96 10 93 53 82
94 15 96 69 9
74 0 62 38 96
37 54 55 82 38
Spiral 5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9 Sample Output Feldberg: 7
Spiral: 25
这是一道记忆化搜索的题目，dfs搜索每一个点，如果已经搜过的话，直接返回值；dp[i] [j]表示从这个点最多能够走多少步，每搜索一次，dp[i] [j]就加一，直到走不下去为止；
#include<bits/stdc++.h> using namespace std; const int MAXN=100; const int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int a,b; int graph[MAXN+5][MAXN+5]; int dp[MAXN+5][MAXN+5]; int dfs(int x,int y){ if(dp[x][y]){ return dp[x][y]; } int sum=0; for(int i=0;i<4;i++){ int xx=x+d[i][0];int yy=y+d[i][1]; if(xx>=1&&yy>=1&&xx<=a&&yy<=b&&graph[xx][yy]>graph[x][y]){ sum=max(sum,dfs(xx,yy)); } } dp[x][y]+=sum+1; return dp[x][y]; } int main(){ int t; // cin>>t; // while(t--){ string area; // cin>>area; cin>>a>>b; for(int i=1;i<=a;i++){ for(int j=1;j<=b;j++){ cin>>graph[i][j]; } } int ans=0; memset(dp,0,sizeof(dp)); for(int i=1;i<=a;i++){ for(int j=1;j<=b;j++){ ans=max(ans,dfs(i,j)); } } // cout<<area<<": "; cout<<ans<<endl; // } }(If you smiled when you see the title, this problem is for you _) For those who don’t know KTV, see: http://en.wikipedia.org/wiki/Karaoke_box There is one very popular song called Jin Ge Jin Qu(). It is a mix of 37 songs, and is extremely long (11 minutes and 18 seconds) — I know that there are Jin Ge Jin Qu II and III, and some other unofficial versions. But in this problem please forget about them. Why is it popular? Suppose you have only 15 seconds left (until your time is up), then you should select another song as soon as possible, because the KTV will not crudely stop a song before it ends (people will get frustrated if it does so!). If you select a 2-minute song, you actually get 105 extra seconds! …and if you select Jin Ge Jin Qu, you’ll get 663 extra seconds!!! Now that you still have some time, but you’d like to make a plan now. You should stick to the following rules: • Don’t sing a song more than once (including Jin Ge Jin Qu). • For each song of length t, either sing it for exactly t seconds, or don’t sing it at all. • When a song is finished, always immediately start a new song. Your goal is simple: sing as many songs as possible, and leave KTV as late as possible (since we have rule 3, this also maximizes the total lengths of all songs we sing) when there are ties. Input The first line contains the number of test cases T (T ≤ 100). Each test case begins with two positive integers n, t (1 ≤ n ≤ 50, 1 ≤ t ≤ 109), the number of candidate songs (BESIDES Jin Ge Jin Qu) and the time left (in seconds). The next line contains n positive integers, the lengths of each song, in seconds. Each length will be less than 3 minutes — I know that most songs are longer than 3 minutes. But don’t forget that we could manually “cut” the song after we feel satisfied, before the song ends. So here “length” actually means “length of the part that we want to sing”. It is guaranteed that the sum of lengths of all songs (including Jin Ge Jin Qu) will be strictly larger than t. Output For each test case, print the maximum number of songs (including Jin Ge Jin Qu), and the total lengths of songs that you’ll sing. Explanation: In the first example, the best we can do is to sing the third song (80 seconds), then Jin Ge Jin Qu for another 678 seconds. In the second example, we sing the first two (30+69=99 seconds). Then we still have one second left, so we can sing Jin Ge Jin Qu for extra 678 seconds. However, if we sing the first and third song instead (30+70=100 seconds), the time is already up (since we only have 100 seconds in total), so we can’t sing Jin Ge Jin Qu anymore! Sample Input 2
3 100
60 70 80
3 100
30 69 70 Sample Output Case 1: 2 758
Case 2: 3 777
虽然t<=1e9，但是所有n=1首曲子的时间长度严格大于t，所以t实际上不会大于180n+678。这样这道题就可以转化为0—1背包的问题来解决。设dp[i]为时间为i时能够唱的最多的曲子数量，所以状态转移方程为
dp[i]=max(dp[i],dp[i-ti[]j]+1)(ti[j]表示第j首歌的时间)边界为dp[0]=0；
背包容量从t-1开始减，留出的一秒给劲歌金曲；需要注意的是为了输出总的时长，除了0以外dp[i]的值应初始化为-1e9,否则无法正确输出曲子的总长度；
#include<iostream> #include<cstring> const int MAXN=55; const int MAX=10000; const int INF=-1e9; using namespace std; int main(){ int T,n,t,a[MAXN]; int dp[MAX]; cin>>T; for(int i=1;i<=T;i++){ cin>>n>>t; for(int j=1;j<=n;j++){ cin>>a[j]; } int Max=0; for(int j=1;j<=t;j++){ dp[j]=INF; } dp[0]=0; for(int j=1;j<=n;j++){ for(int k=t-1;k>=a[j];k--){//0-1背包 dp[k]=max(dp[k],dp[k-a[j]]+1); if(Max<dp[k])Max=dp[k]; } } for(int j=t-1;j>=0;j--){ if(Max==dp[j]){ cout<<"Case "<<i<<": "<<dp[j]+1<<" "<<j+678<<"\n"; break; } } // for(int j=0;j<=t;j++){ // cout<<dp[j]<<" "; // } } return 0; }Secret agent Maria was sent to Algorithms City to carry out an especially dangerous mission. After several thrilling events we find her in the first station of Algorithms City Metro, examining the time table. The Algorithms City Metro consists of a single line with trains running both ways, so its time table is not complicated. Maria has an appointment with a local spy at the last station of Algorithms City Metro. Maria knows that a powerful organization is after her. She also knows that while waiting at a station, she is at great risk of being caught. To hide in a running train is much safer, so she decides to stay in running trains as much as possible, even if this means traveling backward and forward. Maria needs to know a schedule with minimal waiting time at the stations that gets her to the last station in time for her appointment. You must write a program that finds the total waiting time in a best schedule for Maria. The Algorithms City Metro system has N stations, consecutively numbered from 1 to N. Trains move in both directions: from the first station to the last station and from the last station back to the first station. The time required for a train to travel between two consecutive stations is fixed since all trains move at the same speed. Trains make a very short stop at each station, which you can ignore for simplicity. Since she is a very fast agent, Maria can always change trains at a station even if the trains involved stop in that station at the same time. Input The input file contains several test cases. Each test case consists of seven lines with information as follows. Line 1. The integer N (2 ≤ N ≤ 50), which is the number of stations. Line 2. The integer T (0 ≤ T ≤ 200), which is the time of the appointment. Line 3. N − 1 integers: t1,t2,…,tN−1 (1 ≤ ti ≤ 20), representing the travel times for the trains between two consecutive stations: t1 represents the travel time between the first two stations, t2 the time between the second and the third station, and so on. Line 4. The integer M1 (1 ≤ M1 ≤ 50), representing the number of trains departing from the first station. Line 5. M1 integers: d1,d2,…,dM1 (0 ≤ di ≤ 250 and di < di+1), representing the times at which trains depart from the first station. Line 6. The integer M2 (1 ≤ M2 ≤ 50), representing the number of trains departing from the N-th station. Line 7. M2 integers: e1,e2,…,eM2 (0 ≤ ei ≤ 250 and ei < ei+1) representing the times at which trains depart from the N-th station. The last case is followed by a line containing a single zero. Output For each test case, print a line containing the case number (starting with 1) and an integer representing the total waiting time in the stations for a best schedule, or the word ‘impossible’ in case Maria is unable to make the appointment. Use the format of the sample output. Sample Input 4
55
5 10 15
4
0 5 10 20
4
0 5 10 15
4
18
1 2 3
5
0 3 6 10 12
6
0 3 5 7 12 15
2
30
20
1
20
7
1 3 5 7 11 13 17
0 Sample Output Case Number 1: 5
Case Number 2: 0
Case Number 3: impossible
时间是单向流逝的，是一个天然的序。影响到决策的只有当前的时间和所处的车站，所以可以用d(i,j)表示时刻i，你在车站j（编号1—n），最少还需要等待多长时间。边界条件是d（T,n）=0,其它d(T,0)(i!=n)为正无穷。有如下的三种决策：
决策一：等1分钟
决策二：搭乘开往右开的车（如果有）
决策三：搭乘开往左开的车（如果有）
#include<bits/stdc++.h> const int oo=0x3f3f3f3f; using namespace std; int n,T,M1,M2,kase; int t[55]; bool trainl[55][10010];//train[i][j]:第i站第j时间是否有train bool trainr[55][10010]; int dp[10010][55];//dp[i][j]:在时刻i你在车站j最低等多少时间 int main(){ while(cin>>n && n!=0){ kase++; cin>>T; memset(t, 0, sizeof(t)); memset(trainl, 0, sizeof(trainl)); memset(trainr, 0, sizeof(trainr)); for(int i=1; i<=n-1; i++) cin>>t[i];//t[i]:i~i+1站时间 cin>>M1; for(int i=1; i<=M1; i++){ int t1;//左站出发时间 cin>>t1; int sum=t1; for(int j=1; j<=n; j++){ trainl[j][sum] = 1; sum+=t[j]; } } cin>>M2; for(int i=1; i<=M2; i++){ int t2;//右站出发时间 cin>>t2; int sum=t2; for(int j=n; j>=1; j--){ trainr[j][sum] = 1; sum+=t[j-1]; } } for(int i=1; i<=n-1; i++) dp[T][i]=oo; dp[T][n] = 0; for(int i=T-1; i>=0; i--) for(int j=1; j<=n; j++){ dp[i][j]=dp[i+1][j]+1; if(j<n && trainl[j][i] && i+t[j]<=T ) dp[i][j] = min(dp[i][j], dp[i+t[j]][j+1]); if(j>1 && trainr[j][i] && i+t[j-1]<=T ) dp[i][j] = min(dp[i][j], dp[i+t[j-1]][j-1]); } cout<< "Case Number " << kase<< ": "; if(dp[0][1] >= oo) cout<< "impossible\n"; else cout<<dp[0][1] <<"\n"; } return 0; }You have to cut a wood stick into pieces. The most affordable company, The Analog Cutting Machinery, Inc. (ACM), charges money according to the length of the stick being cut. Their procedure of work requires that they only make one cut at a time. It is easy to notice that different selections in the order of cutting can led to different prices. For example, consider a stick of length 10 meters that has to be cut at 2, 4 and 7 meters from one end. There are several choices. One can be cutting first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 meters, the resulting of 8 and the last one of 6. Another choice could be cutting at 4, then at 2, then at 7. This would lead to a price of 10 + 4 + 6 = 20, which is a better price. Your boss trusts your computer abilities to find out the minimum cost for cutting a given stick. Input The input will consist of several input cases. The first line of each test case will contain a positive number l that represents the length of the stick to be cut. You can assume l < 1000. The next line will contain the number n (n < 50) of cuts to be made. The next line consists of n positive numbers ci (0 < ci < l) representing the places where the cuts have to be done, given in strictly increasing order. An input case with l = 0 will represent the end of the input. Output You have to print the cost of the optimal solution of the cutting problem, that is the minimum cost of cutting the given stick. Format the output as shown below.
Input The input will consist of several input cases. The first line of each test case will contain a positive number l that represents the length of the stick to be cut. You can assume l < 1000. The next line will contain the number n (n < 50) of cuts to be made. The next line consists of n positive numbers ci (0 < ci < l) representing the places where the cuts have to be done, given in strictly increasing order. An input case with l = 0 will represent the end of the input. Output You have to print the cost of the optimal solution of the cutting problem, that is the minimum cost of cutting the given stick. Format the output as shown below. Sample Input 100
3
25 50 75
10
4
4 5 7 8
0 Sample Output The minimum cutting is 200.
The minimum cutting is 22.
经典的区间dp；思想应该是倒着拼起来，因为切一刀切成两个的代价就是两个小的拼起来的长度；所以用dp[i] [j]表示切割小木棍i~j的最小代价，状态转移方程为：
dp(i,j)=min(dp(i,j),dp(i,k)+dp(k,j)+a[j]-a[i]);边界为dp[i] [i+1]=0;其余的点初始化为INF；
#include<iostream> using namespace std; const int MAXN=60; int dp[MAXN][MAXN]; const int INF=0x3f3f3f3f; int main(){ int len,n; int a[MAXN]; while(cin>>len&&len){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } a[0]=0;a[n+1]=len; for(int i=1;i<=n+1;i++){//首先枚举长度 for(int j=0;j+i<=n+1;j++){ dp[j][j+i]=INF;//初始化为一个极大值 if(i==1)dp[j][j+i]=0;//相邻两个点费用为0，相当于已经切好的一段，不能再切了 else{ for(int k=j+1;k<j+i;k++)//枚举中间的点 dp[j][j+i]=min(dp[j][j+i],dp[j][k]+dp[k][j+i]+a[j+i]-a[j]); } } } cout<<"The minimum cutting is "<<dp[0][n+1]<<".\n"; } return 0; }You are given the task to design a lighting system for a huge conference hall. After doing a lot of calculation and sketching, you have figured out the requirements for an energy-efficient design that can properly illuminate the entire hall. According to your design, you need lamps of n different power ratings. For some strange current regulation method, all the lamps need to be fed with the same amount of current. So, each category of lamp has a corresponding voltage rating. Now, you know the number of lamps and cost of every single unit of lamp for each category. But the problem is, you are to buy equivalent voltage sources for all the lamp categories. You can buy a single voltage source for each category (Each source is capable of supplying to infinite number of lamps of its voltage rating.) and complete the design. But the accounts section of your company soon figures out that they might be able to reduce the total system cost by eliminating some of the voltage sources and replacing the lamps of that category with higher rating lamps. Certainly you can never replace a lamp by a lower rating lamp as some portion of the hall might not be illuminated then. You are more concerned about money-saving than energy-saving. Find the minimum possible cost to design the system. Input Each case in the input begins with n (1 ≤ n ≤ 1000), denoting the number of categories. Each of the following n lines describes a category. A category is described by 4 integers - V (1 ≤ V ≤ 132000), the voltage rating, K (1 ≤ K ≤ 1000), the cost of a voltage source of this rating, C (1 ≤ C ≤ 10), the cost of a lamp of this rating and L (1 ≤ L ≤ 100), the number of lamps required in this category. The input terminates with a test case where n = 0. This case should not be processed.
Output For each test case, print the minimum possible cost to design the system. Sample Input 3
100 500 10 20
120 600 8 16
220 400 7 18
0 Sample Output 778
简单dp；首先有一个结论，某种灯泡，要么不换，要么全换；如果只换部分，那就需要两种电源，很明显这样不划算。只有电压高的灯泡能换成电压低的，反过来不可以。
先把灯泡按照电压从小到大排序，设s[i]表示前i种灯泡的数量。设dp[i]表示第1i种灯泡的最小开销，则状态转移方程为dp[i]=min(dp[i],dp[j]+(s[i]-s[j])*c[i]=k[i])，表示前j个都用最优方案买，然后第j+1i个都用第i号电源。
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int MAXN=1005; const int INF=0x3f3f3f3f; struct node{ int v; int k; int c; int l; }a[MAXN]; bool cmp(node a,node b){ return a.v<b.v; } int sum(int x){ int ans=0; for(int i=1;i<=x;i++){ ans+=a[i].l; } return ans; } int dp[MAXN]; int main(){ int t,s[MAXN]; while(cin>>t&&t){ memset(dp,0,sizeof(dp)); memset(s,0,sizeof(s)); for(int i=1;i<=t;i++){ cin>>a[i].v>>a[i].k>>a[i].c>>a[i].l; } sort(a+1,a+t+1,cmp); for(int i=1;i<=t;i++){ s[i]=sum(i); dp[i]=INF; } dp[0]=0; for(int i=1;i<=t;i++){ for(int j=0;j<=i;j++){ dp[i]=min(dp[i],dp[j]+(s[i]-s[j])*a[i].c+a[i].k); } } cout<<dp[t]<<"\n"; } return 0; }Problemsthatrequireminimumpathsthroughsomedomainappearinmanydifferentareasofcomputer science. For example, one of the constraints in VLSI routing problems is minimizing wire length. The Traveling Salesperson Problem (TSP) — finding whether all the cities in a salesperson’s route can be visited exactly once with a specified limit on travel time — is one of the canonical examples of an NP-complete problem; solutions appear to require an inordinate amount of time to generate, but are simple to check. This problem deals with finding a minimal path through a grid of points while traveling only from left to right. Given an m×n matrix of integers, you are to write a program that computes a path of minimal weight. A path starts anywhere in column 1 (the first column) and consists of a sequence of steps terminating in column n (the last column). A step consists of traveling from column i to column i + 1 in an adjacent (horizontal or diagonal) row. The first and last rows (rows 1 and m) of a matrix are considered adjacent, i.e., the matrix “wraps” so that it represents a horizontal cylinder. Legal steps are illustrated on the right. The weight of a path is the sum of the integers in each of the n cells of the matrix that are visited. Forexample,twoslightlydifferent 5×6 matricesareshownbelow(theonlydifferenceisthenumbers in the bottom row)
The minimal path is illustrated for each matrix. Note that the path for the matrix on the right takes advantage of the adjacency property of the first and last rows.
Input The input consists of a sequence of matrix specifications. Each matrix specification consists of the row and column dimensions in that order on a line followed by m·n integers where m is the row dimension and n is the column dimension. The integers appear in the input in row major order, i.e., the first n integers constitute the first row of the matrix, the second n integers constitute the second row and so on. The integers on a line will be separated from other integers by one or more spaces. Note: integers are not restricted to being positive. There will be one or more matrix specifications in an input file. Input is terminated by end-of-file. Foreachspecificationthenumberofrowswillbebetween1and10inclusive; thenumberofcolumns will be between 1 and 100 inclusive. No path’s weight will exceed integer values representable using 30 bits.
Output Two lines should be output for each matrix specification in the input file, the first line represents a minimal-weightpath, andthesecondlineisthecostofaminimalpath. Thepathconsistsofasequence of n integers(separatedbyoneormorespaces)representingtherowsthatconstitutetheminimalpath. If there is more than one path of minimal weight the path that is lexicographically smallest should be output. Note: Lexicographically means the natural order on sequences induced by the order on their elements.
Sample Input
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3
2 2
9 10
9 10
Sample Output
1 2 3 4 4 5
16
1 2 1 5 4 5
11
1 1
19
简单dp，类似于数塔问题，问从最左边走到最右边花费的最小代价。区别在于这里的第一行和最后一行是连起来的，第一行向上走是最后一行，最后一行向下走是第一行，形成了一个环。设dp[i] [j]表示从（i，j）到最右边的最小花费，需要递推，从最后一列往左推。
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int MAXN=100; const int INF=0x3f3f3f3f; int m,n; int graph[MAXN][MAXN]; int dp[MAXN][MAXN]; int main(){ while(cin>>m>>n){ for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ cin>>graph[i][j]; } } memset(dp,0,sizeof(dp)); int next[MAXN][MAXN],ans=INF,first=0;//next[i][j]保存的是后面一列的行号 memset(next,0,sizeof(next)); for(int j=n-1;j>=0;j--){//逆推 for(int i=0;i<=m-1;i++){ if(j==n-1)dp[i][j]=graph[i][j];//边界 else{ dp[i][j]=INF; int row[3]={i,i-1,i+1}; if(i==0)row[1]=m-1; if(i==m-1)row[2]=0; sort(row,row+3);//重新排序，便于找到字典序最小的 for(int k=0;k<=2;k++){ int v=dp[row[k]][j+1]+graph[i][j]; if(v<dp[i][j]){ dp[i][j]=v; next[i][j]=row[k]; } } } if(j==0){ if(ans>dp[i][j]){ ans=dp[i][j];first=i; } } } } cout<<first+1;//输出第一列 for(int i=next[first][0],j=1;j<=n-1;i=next[i][j],j++){ cout<<" "<<i+1;//输出其它列 } cout<<"\n"<<ans<<"\n"; } return 0; }A couple of years ago, a new world wide crisis started, leaving many people with economical problems. Some workers of a particular company are trying to ask for an increase in their salaries. The company has a strict hierarchy, in which each employee has exactly one direct boss, with the exception of the owner of the company that has no boss. Employees that are not bosses of any other employee are called workers. The rest of the employees and the owner are called bosses. To ask for a salary increase, a worker should file a petition to his direct boss. Of course, each boss is encouraged to try to make their subordinates happy with their current income, making the company’s profit as high as possible. However, when at least T percent of its direct subordinates have filed a petition, that boss will be pressured and have no choice but to file a petition himself to his own direct boss. Each boss files at most 1 petition to his own direct boss, regardless on how many of his subordinates filed him a petition. A boss only accounts his direct subordinates (the ones that filed him a petition and the ones that didn’t) to calculate the pressure percentage. Note that a boss can have both workers and bosses as direct subordinates at the same time. Such a boss may receive petitions from both kinds of employees, and each direct subordinate, regardless of its kind, will be accounted as 1 when checking the pressure percentage. When a petition file gets all the way up to the owner of the company, all salaries are increased. The workers’ union is desperately trying to make that happen, so they need to convince many workers to file a petition to their direct boss. Given the company’s hierarchy and the parameter T, you have to find out the minimum number of workers that have to file a petition in order to make the owner receive a petition. Input There are several test cases. The input for each test case is given in exactly two lines. The first line contains two integers N and T (1 ≤ N ≤ 105 , 1 ≤ T ≤ 100), separated by a single space. N indicates the number of employees of the company (not counting the owner) and T is the parameter described above. Each of the employees is identified by an integer between 1 and N. The owner is identified by the number 0. The second line contains a list of integers separated by single spaces. The integer Bi, at position i on this list (starting from 1), indicates the identification of the direct boss of employee i (0 ≤ Bi ≤ i−1). The last test case is followed by a line containing two zeros separated by a single space. Output For each test case output a single line containing a single integer with the minimum number of workers that need to file a petition in order to get the owner of the company to receive a petition. Sample Input 3 100
0 0 0
3 50
0 0 0
14 60
0 0 1 1 2 2 2 5 7 5 7 5 7 5
0 0 Sample Output 3
2
5
本题为树状dp.设dp[u]为让u给上级发信至少需要多少个工人。假设u有k个子节点，则至少需要c=(kt-1)/100+1个直接下属发信才行。把所有的子节点的d值进行排序，把前c个加起来就行。
#include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int MAXN=1e5; vector<int> graph[MAXN+5]; int n,t; int dp(int u){ if(graph[u].empty()) return 1; int k=graph[u].size(); vector<int> d; for(int i=0;i<k;i++){ d.push_back(dp(graph[u][i])); } sort(d.begin(),d.end()); int c=(k*t-1)/100+1;//向上取整 int ans=0; for(int i=0;i<c;i++){ ans+=d[i]; } return ans; } int main(){ while(cin>>n>>t&&n+t){ for(int i=0;i<=n;i++){//从0开始clear; graph[i].clear(); } int a; for(int i=1;i<=n;i++){ cin>>a; graph[a].push_back(i); } cout<<dp(0)<<"\n"; } return 0; }We say a sequence of characters is a palindrome if it is the same written forwards and backwards. For example, ‘racecar’ is a palindrome, but ‘fastcar’ is not. A partition of a sequence of characters is a list of one or more disjoint non-empty groups of consecutive characters whose concatenation yields the initial sequence. For example, (‘race’, ‘car’) is a partition of ‘racecar’ into two groups. Given a sequence of characters, we can always create a partition of these characters such that each group in the partition is a palindrome! Given this observation it is natural to ask: what is the minimum number of groups needed for a given string such that every group is a palindrome? For example: • ‘racecar’ is already a palindrome, therefore it can be partitioned into one group. • ‘fastcar’ does not contain any non-trivial palindromes, so it must be partitioned as (‘f’, ‘a’, ‘s’, ‘t’, ‘c’, ‘a’, ‘r’). • ‘aaadbccb’ can be partitioned as (‘aaa’, ‘d’, ‘bccb’). Input Input begins with the number n of test cases. Each test case consists of a single line of between 1 and 1000 lowercase letters, with no whitespace within. Output For each test case, output a line containing the minimum number of groups required to partition the input into groups of palindromes. Sample Input 3
racecar
fastcar
aaadbccb Sample Output 1
7
3
简单dp。设dp[i]表示第0~i个中间最小回文字符串的个数，那么状态转移方程为：
dp[i]=min(dp[i],dp[j]+1)(j+1到i是回文字符串)
#include<iostream> #include<cstring> using namespace std; const int MAXN=1005; const int INF=0x3f3f3f3f; int n; string s; int dp[MAXN]; bool check(int l,int r){ while(l<r){ if(s[l]!=s[r])return 0; l++;r--; } return 1; } int main(){ cin>>n; while(n--){ cin>>s; for(int i=1;i<=s.size()-1;i++){ dp[i]=INF; } dp[0]=1; for(int i=1;i<=s.size()-1;i++){ if(check(0,i)){ dp[i]=1;continue;//检查0~i本身是否为回文字符串，如果是则dp[i][j]=1,直接continue } for(int j=0;j<i;j++){ if(check(j+1,i))dp[i]=min(dp[i],dp[j]+1); } } cout<<dp[s.size()-1]<<"\n"; } return 0; }John Doe, a skilled pilot, enjoys traveling. While on vacation, he rents a small plane and starts visiting beautiful places. To save money, John must determine the shortest closed tour that connects his destinations. Each destination is represented by a point in the plane pi =< xi,yi >. John uses the following strategy: he starts from the leftmost point, then he goes strictly left to right to the rightmost point, and then he goes strictly right back to the starting point. It is known that the points have distinct x-coordinates. Write a program that, given a set of n points in the plane, computes the shortest closed tour that connects the points according to John’s strategy. Input The program input is from a text file. Each data set in the file stands for a particular set of points. For each set of points the data set contains the number of points, and the point coordinates in ascending order of the x coordinate. White spaces can occur freely in input. The input data are correct. Output For each set of data, your program should print the result to the standard output from the beginning of a line. The tour length, a floating-point number with two fractional digits, represents the result. Note: An input/output sample is in the table below. Here there are two data sets. The first one contains 3 points specified by their x and y coordinates. The second point, for example, has the x coordinate 2, and the y coordinate 3. The result for each data set is the tour length, (6.47 for the first data set in the given example). Sample Input 3
1 1
2 3
3 1
4
1 1
2 3
3 1
4 2 Sample Output 6.47
7.89
“从左到右再回来”不太方便思考，可以改成：两个人同时从最左点出发，沿着两条不同的路径走，最后都走到最右点，而且除了起点和终点外其余每个点恰好被一个人经过。这样，就可以用d(i,j)表示第一个人走到i，第二个人走到j还需要走多远的距离。
注意，为了每一个点都走到，我们规定i>j同时两个人下一步只能走到i+1;
状态转移方程为：d(i,j)=min(d(i+1,i)+dist(i+1,j).d(i+1,j)+dist(i+1,i))
其边界为d(n-1,j)=dist(n,n-1)+dist(n,j).
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int MAXN=105; struct node{ int x,y; }a[MAXN]; double dp[MAXN][MAXN]; double dist(node a,node b){ double x=fabs(a.x-b.x)*1.0; double y=fabs(a.y-b.y)*1.0; return sqrt(x*x+y*y); } int main(){ int n; while(cin>>n){ memset(a,0,sizeof(0)); for(int i=1;i<=n;i++){ cin>>a[i].x>>a[i].y; } for(int i=1;i<=n-2;i++){ dp[n-1][i]=dist(a[n-1],a[n])+dist(a[n],a[i]); } for(int i=n-2;i>=2;i--){ for(int j=i-1;j>=1;j--){ dp[i][j]=min(dp[i+1][i]+dist(a[j],a[i+1]),dp[i+1][j]+dist(a[i],a[i+1])); } } printf("%.2lf\n",dp[2][1]+dist(a[2],a[1])); } return 0; }