本文正體字版由OpenCC轉換
==1031==
動態規劃，設定F[i]爲到達第i個城市的最小花費，從第S個城市開始，到第T個城市結束
注意有可能S<T，要交換S和T。
狀態轉移方程 F[i]=Min{ F[k] + Cost } (k=i-1..S)
具體Cost取決與i與k城市的距離，如果距離已經大於L3，可以跳出。
邊界條件 F[S]=0
目標結果 Ans=F[T]
==1039==
樹形動態規劃，可以用左孩子右兄弟表示法來存儲樹形結構。
狀態設定
F[i,j]表示以第i個人爲根的子樹中，第i個人是否(j=0不包含，j=1包含)來參加聚會的快樂度總和的最大值 Happy[i]爲第i個人的快樂度
狀態轉移方程
F[i,1]=Sum{ F[k,0] } + Happy[i] F[i,0]=Sum{ Max{ F[k,0],F[k,1] } }
k爲i的所有子節點
目標結果
Ans=Max{ F[root,0],F[root,1] } root爲根節點
==1056==
樹形動態規劃，可以用左孩子右兄弟上父親表示爲一棵二叉樹。
狀態設定 F[i]爲i點向下可以到達的最遠的點的距離，其實就是子樹的最大深度。 G[i]爲i點向上可以到達的最遠的點的距離，向上走至少一步以後可以向下走其他的分支，目的是取消後效性。
狀態轉移方程
F[i]=Max{ F[i.孩子] } + 1 G[i]=Max{ G[i.父親] + 1 , F[i.兄弟] + 2 }
邊界條件
F[k]=0 (k爲葉結點) G[1]=0
目標結果
所有滿足Max{ F[i] , G[i] }爲最小值的i (i=1..N)
==1073==
類似於揹包的動態規劃。
狀態設定 F[i] 要購買的土地面積爲i時，最少的土地所有證書個數
狀態轉移方程 F[i]=Min{ F[i-aa] } + 1 (1<=aa<=i)
邊界條件 F[0]=0
目標結果 F[N]
==1078==
想出這道題需要敏銳的洞察力。求出包含最長的線段序列，結尾不能重複。我們把所有的線段按左關鍵字排序，然後對線段的右關鍵字求最長單調下降序列，就是結果。
因爲對左關鍵字排序就確定了前面的線段一定不會是後面線段的子線段，而右關鍵字單調下降正說明了前面的線段嚴格包含後面的線段。所以右關鍵字的最長單調下降序列就是結果。求最長單調下降序列時要保存每個狀態的前驅狀態，以求出完整的序列。
狀態設定 F[i] 爲以第i個數爲結尾的最長下降序列 H[i] 爲第i個線段的右關鍵字，即第i個數
狀態轉移方程 F[i]=Max{ F[j] } + 1 (j=1..i-1)
目標結果 Max{ F[i] } (i=1..N)
以下是程序
1031
#include <iostream>
#define MAX 10001
#define INF 0x7FFFFFFF
using namespace std;
typedef unsigned long Number;
Number N,S,T,C1,C2,C3,L1,L2,L3,Ans,p;
Number F[MAX],D[MAX];
void init()
{
freopen("1031.in","r",stdin);
freopen("1031.out","w",stdout);
cin >> L1 >> L2 >> L3 >> C1 >> C2 >> C3;
cin >> N >> S >> T;
if (S>T)
{
p=S;
S=T;
T=p;
}
for (int i=2;i<=N;i++)
{
scanf("%d",&D[i]);
}
}
void dynamic()
{
int i,k;
F[S]=0;
for (i=S+1;i<=T;i++)
{
F[i]=INF;
for (k=i-1;k>=S;k--)
{
if (D[i]-D[k]<=L1)
{
if (F[k]+C1<F[i])
F[i]=F[k]+C1;
}
else if (D[i]-D[k]<=L2)
{
if (F[k]+C2<F[i])
F[i]=F[k]+C2;
}
else if (D[i]-D[k]<=L3)
{
if (F[k]+C3<F[i])
F[i]=F[k]+C3;
}
else
{
break;
}
}
}
Ans=F[T];
}
int main()
{
init();
dynamic();
cout << Ans << endl;
return 0;
}
1039
#include <iostream>
#define MAX 6001
using namespace std;
class node
{
public:
node *left,*right;//左孩子右兄弟
int v,id;
node(int i,int t)
{
left=right=0;
v=t;
id=i;
}
};
node *P[MAX];
int N,Ans;
int F[MAX][2];
bool nr[MAX];
void init()
{
int i,v,a,b;
freopen("1039.in","r",stdin);
freopen("1039.out","w",stdout);
scanf("%d",&N);
for (i=1;i<=N;i++)
{
scanf("%d",&v);
P[i]=new node(i,v);
F[i][0]=F[i][1]=-1;
}
while (1)
{
scanf("%d%d",&a,&b);
nr[a]=true;
if (a==0 && b==0)
break;
if (!P[b]->left)
{
P[b]->left=P[a];
}
else
{
P[a]->right=P[b]->left->right;
P[b]->left->right=P[a];
}
}
for (i=1;i<=N;i++)
{
if (!nr[i])
{
P[0]=new node(0,0);
P[0]->left=P[i];
break;
}
}
}
int dp(int i,int w)
{
int j,max,sum=0;
node *k;
if (w)
sum+=P[i]->v;
for (k=P[i]->left;k;k=k->right)
{
j=k->id;
if (F[j][0]==-1)
F[j][0]=dp(j,0);
max=F[j][0];
if (!w)
{
if (F[j][1]==-1)
F[j][1]=dp(j,1);
if (F[j][1]>max)
max=F[j][1];
}
sum+=max;
}
return sum;
}
int main()
{
init();
Ans=dp(0,0);
cout << Ans << endl;
return 0;
}
1056
#include <iostream>
#define MAX 10001
#define INF 0x7FFFFFFF
using namespace std;
class node
{
public:
node *left,*right,*father;//左孩子 右兄弟 上父親
int id;
node(int i)
{
left=right=father=0;
id=i;
}
};
node *P[MAX];
int F[MAX],G[MAX];
int Ans[MAX],Ac=0;
int N;
void init()
{
int i,f;
freopen("1056.in","r",stdin);
freopen("1056.out","w",stdout);
scanf("%d",&N);
P[1]=new node(1);
F[1]=G[1]=-1;
for (i=2;i<=N;i++)
{
scanf("%d",&f);
P[i]=new node(i);
P[i]->father=P[f];
if (!P[f]->left)
{
P[f]->left=P[i];
}
else
{
P[i]->right=P[f]->left->right;
P[f]->left->right=P[i];
}
F[i]=G[i]=-1;
}
}
int dp(int i)
{
int j,max=-1;
node *k;
for (k=P[i]->left;k;k=k->right)
{
j=k->id;
if (F[j]==-1)
F[j]=dp(j);
if (F[j]>max)
max=F[j];
}
return max+1;
}
int dynamic(int i)
{
int j,max=0;
node *k;
k=P[i]->father;
if (k)
{
j=k->id;
if (G[j]==-1)
G[j]=dynamic(j);
max=G[j]+1;
for (k=k->left;k;k=k->right)
{
if (k==P[i]) continue;
j=k->id;
if (F[j]+2>max)
max=F[j]+2;
}
}
return max;
}
void solve()
{
int i,min=INF,v;
F[1]=dp(1);
for (i=1;i<=N;i++)
{
if (G[i]==-1)
{
G[i]=dynamic(i);
}
}
for (i=1;i<=N;i++)
{
v=F[i] > G[i] ? F[i] : G[i];
if (v<min)
{
min=v;
Ans[Ac=1]=i;
}
else if (v==min)
{
Ans[++Ac]=i;
}
}
}
int main()
{
init();
solve();
for (int i=1;i<=Ac;i++)
printf("%d ",Ans[i]);
return 0;
}
1073
#include <iostream>
#define MAX 60001
#define INF 0x7FFFFFFF
using namespace std;
int F[MAX];
int N;
void init()
{
freopen("1073.in","r",stdin);
freopen("1073.out","w",stdout);
cin >> N;
}
void dynamic()
{
int i,a,min;
for (i=1;i<=N;i++)
{
min=INF;
for (a=1;a*a<=i;a++)
{
if (F[i-a*a]<min)
min=F[i-a*a];
}
F[i]=min+1;
}
}
int main()
{
init();
dynamic();
cout << F[N] << endl;
return 0;
}
1078
#include <iostream>
#define MAX 501
using namespace std;
typedef struct
{
int l,r,id;
}seg;
seg S[MAX],A[MAX];
int F[MAX],G[MAX];
int N,Ans;
inline int cmp(const void *a,const void *b)
{
if (((seg *)a)->l == ((seg *)b)->l)
return ((seg *)a)->r - ((seg *)b)->r;
return ((seg *)a)->l - ((seg *)b)->l;
}
void init()
{
int i;
freopen("1078.in","r",stdin);
freopen("1078.out","w",stdout);
scanf("%d",&N);
for (i=1;i<=N;i++)
{
scanf("%d%d",&S[i].l,&S[i].r);
S[i].id=i;
}
qsort(S+1,N,sizeof(S[0]),cmp);
}
void dynamic()//最長單調序列
{
int i,j,k;
for (i=1;i<=N;i++)
{
F[i]=0;
for (j=1;j<=i-1;j++)
{
if (S[j].r>S[i].r && F[j]>F[i])
{
F[i]=F[j];
G[i]=j;
}
}
F[i]++;
if (F[i]>Ans)
{
Ans=F[i];
for (j=Ans,k=i;j>=1;j--,k=G[k])
{
A[j].r=S[k].id;
A[j].l=S[k].r-S[k].l;
}
}
}
qsort(A+1,Ans,sizeof(A[0]),cmp);
cout << Ans << endl;
for (i=1;i<=Ans;i++)
cout << A[i].r << ' ';
}
int main()
{
init();
dynamic();
return 0;
}
上次修改時間 2017-02-03