Ural 1031 1039 1056 1073 1078
This post is written in Chinese. Please consider using Google Translate
==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;
}