第九章 动态规划初步

第九章 动态规划初步

9.2DGA上的动态规划

例题9-1 城市里的间谍 uva1025

主算法是dp，有个预处理数组就是看往左环视往右的时候在时刻i的车站j上有没有车

#includeusing namespace std;int dp[220][55];int visit[220][55][2];int t[220],d1[55],d2[55];const int INF = 0x3f3f3f3f;int main(){ int n,T; int M1,M2; int k=1; while(~scanf("%d",&n)&&n){ scanf("%d",&T); for(int i=1;i=1;j--){ temp+=t[j]; if(temp<=T) visit[temp][j][1]=1; else break; } } for(int i=1;i<=n;i++) dp[T][i]=INF; 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(j1&&visit[i][j][1]&&i+t[j-1]<=T) dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]); } } if(dp[0][1]>=INF) printf("Case Number %d: impossible\n",k++); else printf("Case Number %d: %d\n",k++,dp[0][1]); } return 0;}

例题9-2 巴比伦塔 uva437

DAG不固定起点的最长路径算法：

d(i)表示从节点i处罚的最长路长度，第一步只能走到它相邻的点 d(i)=max(d(j)

#includeusing namespace std;int G[100][100];int d[100];int n,m;//int dp(int i){    int &ans=d[i];    if(ans > 0) return ans;    ans=1;    for(int j=1;j<=n;j++)        if(G[i][j]) ans = max(ans,dp(j)+1);    return ans;}//输出字典序最小的路径void print_ans(int i){    printf("%d ",i);    for(int j=1;j<=n;j++) if(G[i][j]&&d[i]==d[j]+1)    {        print_ans(j);        break;    }}int main(){    scanf("%d%d",&n,&m);    while(m--){        int x,y;        scanf("%d%d",&x,&y); G[x][y]=1;    }    memset(d,0,sizeof(d));    int maxx=0,I;    //输出的是最长长度    for(int i=1;i<=n;i++) dp(i);    for(int i=1;i<=n;i++){        printf("%d ",d[i]);        if(d[i]>maxx) { I=i; maxx=max(d[i],maxx); }    }    print_ans(I);    return 0;}/*5 41 21 33 44 54541 22 33 44 55*/
uva437:
#includeusing namespace std;struct node{    int x,y,z;    void f(int a,int b,int c){ x=a,y=b,z=c; }}st[200];bool cmp(node a,node b){    if(a.x*a.y < b.x*b.y) return 1; return 0;}int n,m,x,y,z,dp[200];int main(){    int flag=1;    while(scanf("%d",&n)&&n){        m=0;        int i,j;        for(i=0;ist[j].x &&st[i].y>st[j].y)                dp[i]=max(dp[i],dp[j]+st[i].z);                if(dp[i]>t) t=dp[i];        }        printf("Case %d: maximum height = %d\n",flag++,t);    }    return 0;}
例题9-3 旅行  uva1347
平面上有n个坐标均为正数的点，按照x坐标从小到大一次给出。求一条最短路线，从最左边的点出发到最右边的点，再回到最左边的点。除了第一个和最右一个点其他点恰好只经过一次。
分析：
可以等效为两个人从第一个点出发，沿不同的路径走到最右点。
d(i, j)表示点1~max(i, j)这些点全部都走过，而且两人的位置分别是i和j，最少还需要走多长的距离。由这个定义可知，d(i, j) == d(j, i)，所以我们再加一个条件，d(i, j)中i>j
这样状态d(i, j)只能转移到d(i+1, j)和d(i+1, i)
边界：d(n-1, j) = dist(n-1, n) + dist(j, n) (1 ≤ j < n-1)
最终所求答案就是dist(1, 2) + d(1, 2)
多阶段决策问题：
多段图的最短路
例题9-4 单向TSP uva116
01背包问题
物品无限的背包问题
固定终点的最长路和最短路
int dp(int S){    if(vis[S]) return d[S]; vis[S]=1;    int& ans=d[S];    ans =1(1<<30);    for(int i=1;i<=n;i++) if(S>=V[i]) ans=max(ans,dp[S-V[i]]+1);    return ans;}
记忆化搜索递推求最大最小两个值
const int INF = 0x3f3f3f3f;minv[0]=maxv[0]=0;for(int i=1;i<=S;i++) minv[i]=INF,maxv[i]=-INF;for(int i=1;i<=S;i++)    for(int j=1;j<=n;j++)if(i>=V[j]) {    minv[i]=min(minv[i],min[i-V[j] ]+1);    maxv[i]=min(maxv[i],max[i-V[j] ]+1);}printf("%d %d\n",minv[S],maxv[S]);//输出字典序最小方案void print_ans(int *d,int S){    for(int i=1;i<=n;i++)    if(S>=V[i]&&d[S]==d[S-V[i]]+1){        printf("%d",i);        print_ans(d,s-v[i]);        break;    }}
时间换空间，减少了输出时的循环
for(int i=1;i<=S;i++)    for(int j=1;j<=n;j++)if(i>=V[j]){    if(min[i]>minp[i-V[j]]+1){        min[i]=min[i-v[j] ]+1;        min_coin[i]=j;    }    if(max[i]
例题9-5 金歌劲曲 uva12563
#includeusing namespace std;int n,t;int v[55];int d[55][10000];int path[55][10000];int main(){    int tt;    scanf("%d",&tt);    for(int kase=1;kase<=tt;kase++)    {        scanf("%d%d",&n,&t);        memset(path,0,sizeof(path));        memset(d,0,sizeof(d));        memset(v,0,sizeof(v));        for(int i=1;i<=n;i++) scanf("%d",&v[i]);        for(int i=n;i>=1;i--)            for(int j=0;j<=t;j++)        {            d[i][j]=(i==n)?0:d[i+1][j];            path[i][j]=path[i+1][j];            if(j>=v[i]){                if(d[i][j]=0;i--)    {      if(d[1][i]==d[1][t-1])      {        if(max_
更多经典模型
最长上升子序列问题LIS
最长公共子序列问题LCS
例题9-6 照明系统设计 uva11400
#includeusing namespace std;#define maxn 1010struct lamp{    int v,k,c,l;}a[maxn];int n,v1,k1,c1,l1;int s[maxn];int d[maxn];bool cmp(lamp a1,lamp a2){    return a1.v
例题9-7划分回文串  uva11584
加一个判断s[i~j]是否是回文串的预处理，把复杂度降到n*n、
#includeusing namespace std;#define MAXN 1010char str[MAXN];int f[MAXN];bool isPalind(int l,int r){    while(l
例题9-8 颜色的长度 uva1625
最优矩阵链乘
最优子结构：
f(i,j)=min{f(i,k)+f(k+1,j)+pi-1pkpj}
最优三角剖分
例题9-9 切木棍 uva10003
#include#includeconst int INF=99999999;const int MN=60;int dp[MN][MN];int num[MN];int main(){    int n,m,i,j,L,p,k,tmp;    int MIN;    while(scanf("%d",&L) && L)    {        scanf("%d",&n);        for(i=1;i<=n;i++) scanf("%d",&num[i]);        num[0]=0;        num[n+1]=L;        memset(dp,0,sizeof(dp));        for(p=1;p<=n+1;p++)           for(i=0;i<=n+1;i++)           {               j=i+p;               MIN=INF;               if(j>n+1) break;//这个很重要               for(k=i+1;ktmp) MIN=tmp;               }               if(MIN!=INF)dp[i][j]=MIN;           }        printf("The minimum cutting is %d.\n",dp[0][n+1]);    }    return 0;}
例题9-10 括号序列 Uva1626
树上的动态规划
树的最大独立集

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。