HDu 4571 Travel in time(グラフィックス+ダイナミックプランニング)
7125 ワード
Travel in time
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 971 Accepted Submission(s): 196
Problem Description
Bob gets tired of playing games, leaves Alice, and travels to Changsha alone. Yuelu Mountain, Orange Island, Window of the World, the Provincial Museum etc...are scenic spots Bob wants to visit. However, his time is very limited, he can’t visit them all.
Assuming that there are N scenic spots in Changsha, Bob defines a satisfaction value Si to each spot. If he visits this spot, his total satisfaction value will plus Si. Bob hopes that within the limited time T, he can start at spot S, visit some spots selectively, and finally stop at spot E, so that the total satisfaction value can be as large as possible. It's obvious that visiting the spot will also cost some time, suppose that it takes C
i units of time to visit spot i ( 0 <= i < N ).
Always remember, Bob can choose to pass by a spot without visiting it (including S and E), maybe he just want to walk shorter distance for saving time.
Bob also has a special need which is that he will only visit the spot whose satisfaction value is
strictly larger than that of which he visited last time. For example, if he has visited a spot whose satisfaction value is 50, he would only visit spot whose satisfaction value is 51 or more then. The paths between the spots are bi-directional, of course.
Input
The first line is an integer W, which is the number of testing cases, and the W sets of data are following.
The first line of each test data contains five integers: N M T S E. N represents the number of spots, 1 < N < 100; M represents the number of paths, 0 < M < 1000; T represents the time limitation, 0 < T <= 300; S means the spot Bob starts from. E indicates the end spot. (0 <= S, E < N)
The second line of the test data contains N integers C
i ( 0 <= C
i <= T ), which means the cost of time if Bob visits the spot i.
The third line also has N integers, which means the satisfaction value Si that can be obtained by visiting the spot i ( 0 <= S
i < 100 ).
The next M lines, each line contains three integers u v L, means there is a bi-directional path between spot u and v and it takes L units of time to walk from u to v or from v to u. (0 <= u, v < N, 0 <= L <= T)
Output
Output case number in the first line (formatted as the sample output).
The second line contains an integer, which is the greatest satisfaction value.
If Bob can’t reach spot E in T units of time, you should output just a “0” (without quotation marks).
Sample Input
1 4 4 22 0 3 1 1 1 1 5 7 9 12 0 1 10 1 3 10 0 2 10 2 3 10
Sample Output
Case #1: 21
Source
2013 ACM-ICPC長沙試合区全国招待試合——テーマ再現
Recommend
zhoujiaqi2010
タイトル:
n個の点mの道からなる無方向図.どの道を歩いても一定の時間がかかります.それぞれのポイントに対応する頂点を見学するのにも一定の時間がかかり、見学ごとに
1つの観光地を終えると満足度があります.t時間内に起点から終点に到達し、得られた最大満足度を求める.
要求:1、毎回訪問する観光地の満足度は前回訪問した観光地の満足度より大きくなければならない.
2、観光地ごとに訪問するか、ただ通るかを選ぶことができます.
分析:
1、要求1のため、観光地を満足度の小さい順に並べなければならない.満足度が等しい場合は、番号サイズでソートします.
2、三点式の思考は、まず出発点からn点までの時間と満足度だけを考慮し、その後、他のアクセス可能な点を挿入することで更新する.
時間と満足度(時間が短ければ短いほど良い----最短の緩和操作、同じ時間で満足度が大きいほど良い).こうしてすべてを
できる経路は時間に応じて満足度が見つかった.最後に、その点から終点に到達する時間に加えて、その点に到達する時間が等しい場合
tはOKです.(まず,i点へのアクセスに相当し,他の点や通過点を通過せずに通過しない場合を考慮する)
3、注意点が多い:
(1)まず重刑です.2つの点の間には複数の道があるかもしれません.
(2)次に,始点と終点の処理である.出発点は訪問しても通ります.スタート地点からspfaを使えば
始点はアクセスであり,後のノードからspfaを開始すると始点はパスである.仮想化を設定します
出発点.
(3)hash配列の使用.
4、状態遷移方程式:dp[i][k]はk時間がi点に到達した満足度を表す.
dp[i][k]=max(dp[i][k],dp[i][k-a[i].c-maps[i][j]]+a[j].v)
感想:
algorithmヘッダファイルのmaxとmin関数を自分で定義したものよりずっと時間がかかることを知った!!
コード:
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 971 Accepted Submission(s): 196
Problem Description
Bob gets tired of playing games, leaves Alice, and travels to Changsha alone. Yuelu Mountain, Orange Island, Window of the World, the Provincial Museum etc...are scenic spots Bob wants to visit. However, his time is very limited, he can’t visit them all.
Assuming that there are N scenic spots in Changsha, Bob defines a satisfaction value Si to each spot. If he visits this spot, his total satisfaction value will plus Si. Bob hopes that within the limited time T, he can start at spot S, visit some spots selectively, and finally stop at spot E, so that the total satisfaction value can be as large as possible. It's obvious that visiting the spot will also cost some time, suppose that it takes C
i units of time to visit spot i ( 0 <= i < N ).
Always remember, Bob can choose to pass by a spot without visiting it (including S and E), maybe he just want to walk shorter distance for saving time.
Bob also has a special need which is that he will only visit the spot whose satisfaction value is
strictly larger than that of which he visited last time. For example, if he has visited a spot whose satisfaction value is 50, he would only visit spot whose satisfaction value is 51 or more then. The paths between the spots are bi-directional, of course.
Input
The first line is an integer W, which is the number of testing cases, and the W sets of data are following.
The first line of each test data contains five integers: N M T S E. N represents the number of spots, 1 < N < 100; M represents the number of paths, 0 < M < 1000; T represents the time limitation, 0 < T <= 300; S means the spot Bob starts from. E indicates the end spot. (0 <= S, E < N)
The second line of the test data contains N integers C
i ( 0 <= C
i <= T ), which means the cost of time if Bob visits the spot i.
The third line also has N integers, which means the satisfaction value Si that can be obtained by visiting the spot i ( 0 <= S
i < 100 ).
The next M lines, each line contains three integers u v L, means there is a bi-directional path between spot u and v and it takes L units of time to walk from u to v or from v to u. (0 <= u, v < N, 0 <= L <= T)
Output
Output case number in the first line (formatted as the sample output).
The second line contains an integer, which is the greatest satisfaction value.
If Bob can’t reach spot E in T units of time, you should output just a “0” (without quotation marks).
Sample Input
1 4 4 22 0 3 1 1 1 1 5 7 9 12 0 1 10 1 3 10 0 2 10 2 3 10
Sample Output
Case #1: 21
Source
2013 ACM-ICPC長沙試合区全国招待試合——テーマ再現
Recommend
zhoujiaqi2010
タイトル:
n個の点mの道からなる無方向図.どの道を歩いても一定の時間がかかります.それぞれのポイントに対応する頂点を見学するのにも一定の時間がかかり、見学ごとに
1つの観光地を終えると満足度があります.t時間内に起点から終点に到達し、得られた最大満足度を求める.
要求:1、毎回訪問する観光地の満足度は前回訪問した観光地の満足度より大きくなければならない.
2、観光地ごとに訪問するか、ただ通るかを選ぶことができます.
分析:
1、要求1のため、観光地を満足度の小さい順に並べなければならない.満足度が等しい場合は、番号サイズでソートします.
2、三点式の思考は、まず出発点からn点までの時間と満足度だけを考慮し、その後、他のアクセス可能な点を挿入することで更新する.
時間と満足度(時間が短ければ短いほど良い----最短の緩和操作、同じ時間で満足度が大きいほど良い).こうしてすべてを
できる経路は時間に応じて満足度が見つかった.最後に、その点から終点に到達する時間に加えて、その点に到達する時間が等しい場合
tはOKです.(まず,i点へのアクセスに相当し,他の点や通過点を通過せずに通過しない場合を考慮する)
3、注意点が多い:
(1)まず重刑です.2つの点の間には複数の道があるかもしれません.
(2)次に,始点と終点の処理である.出発点は訪問しても通ります.スタート地点からspfaを使えば
始点はアクセスであり,後のノードからspfaを開始すると始点はパスである.仮想化を設定します
出発点.
(3)hash配列の使用.
4、状態遷移方程式:dp[i][k]はk時間がi点に到達した満足度を表す.
dp[i][k]=max(dp[i][k],dp[i][k-a[i].c-maps[i][j]]+a[j].v)
感想:
algorithmヘッダファイルのmaxとmin関数を自分で定義したものよりずっと時間がかかることを知った!!
コード:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define INF 10000000
using namespace std;
int dp[105][305];
int maps[105][105];
int hash[105];
typedef struct
{
int c,v,id;
}Point;
Point a[105];
//
bool cmp(Point aa,Point bb)
{
if(aa.v!=bb.v) return aa.v<bb.v;
return aa.id<bb.id;
}
int main()
{
int T,n,m,t,s,e,i,j,k,x,y,z,ans,cnt=1;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d%d",&n,&m,&t,&s,&e);
for(i=0;i<n;i++)
{
scanf("%d",&a[i].c);
a[i].id=i;
}
for(i=0;i<n;i++)
scanf("%d",&a[i].v);
sort(a,a+n,cmp);
for(i=0;i<n;i++)
hash[a[i].id]=i;
s=hash[s];
e=hash[e];
for(i=0;i<n;i++) //
{
for(j=0;j<n;j++)
{
//maps[i][i]=0;
if(i==j) maps[i][j]=0;
else maps[i][j]=INF;
}
}
for(i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
x=hash[x];
y=hash[y];
maps[x][y]=min(z,maps[x][y]);
maps[y][x]=min(z,maps[y][x]);
}
for(k=0;k<n;k++) // (spfa )
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
maps[i][j]=min(maps[i][k]+maps[k][j],maps[i][j]);
}
}
}
printf("Case #%d:
",cnt++);
memset(dp,-1,sizeof(dp));
for(i=0;i<n;i++) // i
{
for(j=a[i].c+maps[i][s];j<=t;j++) // t。
dp[i][j]=a[i].v;
}
for(i=0;i<n;i++)
{
for(j=0;j<i;j++) // j i k
{
if(a[i].v==a[j].v) break;
for(k=0;k<=t;k++) // i k
{
if(maps[i][j]+a[i].c>k)
continue;
if(dp[j][k-maps[i][j]-a[i].c]==-1) continue;
dp[i][k]=max(dp[i][k],dp[j][k-maps[i][j]-a[i].c]+a[i].v);
}
}
}
ans=0;
for(i=0;i<n;i++)
{
for(j=0;j+maps[i][e]<=t;j++) //
{
ans=max(ans,dp[i][j]);
}
}
printf("%d
",ans);
}
return 0;
}
//AC
//609MS