Processing math: 100%

【考试总结】之动规 5 是怎么挂的–litble

于由litble发布

T1

青蛙的烦恼

题目描述：池塘中有 n 片荷叶恰好围成了一个凸多边形，有一只小青蛙恰好站在 1 号荷叶上，小青
蛙想通过最短的路程遍历所有的荷叶（经过一个荷叶一次且仅一次），小青蛙可以从一片荷
叶上跳到另外任意一片荷叶上。
题目分析：
青蛙怎么烦恼的我不知道，反正我很烦恼。
我有一句那啥不知当讲不当讲。
想了一个半小时，
好吧，咱们仔细看看，如果我们用 f(i,j) 表示从 i 到 j 全部遍历一遍，最后停在 i 处的最短路，g(i,j) 表示停在 j 处。
对于 i 到 j 的所有点的最好路径，如果起点和终点中有一个是 i 或者 j，那么就可以转化为 f(i,j) 或者 g(i,j)，那如果起点和终点都不是 i 或者 j 呢？没关系，在动态规划的过程中要用到的就只有 i 或者 j 了。
代码：

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
double x[730],y[730],f[730][730],g[730][730];
int n;
double dis(int a,int b){
    double kl1=x[a]-x[b],kl2=y[a]-y[b];
    return sqrt(kl1*kl1+kl2*kl2);
}
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
    for(i=n;i>=1;i--)
        for(j=i+1;j<=n;j++){
        f[i][j]=min(f[i+1][j]+dis(i+1,i),g[i+1][j]+dis(i,j));
        g[i][j]=min(f[i][j-1]+dis(i,j),g[i][j-1]+dis(j,j-1));
    }
    printf("%.3lf",f[1][n]);
    return 0;
}
C++
Copy

T2

警卫安排

题目描述：一个重要的基地被分为 n 个连通的区域。出于某种神秘的原因，这些区域以一个区域为
核心，呈一颗树形分布。
在每个区域安排警卫所需要的费用是不同的，而每个区域的警卫都可以望见其相邻的区
域，只要一个区域被一个警卫望见或者是安排有警卫，这个区域就是安全的。你的任务是：
在确保所有区域都是安全的情况下，找到安排警卫的最小费用。
题目分析：
还是不难的，就是麻烦了点。
用 f(i,0) 表示 i 节点上安放了警卫
用 f(i,1) 表示 i 节点被其父亲节点看到
用 f(i,2) 表示 i 节点被其儿子节点看到
那么：
f(i,0)=∑min(f(son,0),f(son,1),f(son,2));


f(i,1)=∑min(f(son,0),f(son,2));f

f(i,2)=∑min(f(son,0),f(son,2))+f(k,0);
，k 是 i 的子节点之一
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
#define ll long long
const int maxn=730;
ll w[maxn],f[maxn][3];
int h[maxn],to[maxn],ne[maxn];
bool is[maxn];
int n,rot,tot;
void add(int x,int y){to[++tot]=y;ne[tot]=h[x];h[x]=tot;}
void dfs(int x){
    int i,bj=0;
    for(i=h[x];i;i=ne[i]){
        dfs(to[i]);bj=1;
        f[x][1]+=min(f[to[i]][0],f[to[i]][2]);
        f[x][0]+=min(f[to[i]][0],min(f[to[i]][2],f[to[i]][1]));
    }
    f[x][2]=INT_MAX;
    for(i=h[x];i;i=ne[i])
    f[x][2]=min(f[x][2],f[x][1]-min(f[to[i]][0],f[to[i]][2])+f[to[i]][0]);
    f[x][0]+=w[x];
}
int main()
{
    int i,j,num,x,y;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&x);scanf("%lld%d",&w[x],&num);
        for(j=1;j<=num;j++)
        {scanf("%d",&y);add(x,y);is[y]=1;}
    }
    for(i=1;i<=n;i++)if(!is[i]){rot=i;break;}
    dfs(rot);
    printf("%lld",min(f[rot][0],f[rot][2]));
    return 0;
}
C++
Copy

T3

最长上升子序列

题目描述：LIS 问题是最经典的动态规划基础问题之一。如果要求一个满足一定条件的最长上升子
序列，你还能解决吗？
给出一个长度为 N 整数序列，请求出它的包含第 K 个元素的最长上升子序列。
例如：对于长度为 6 的序列（2,7,3,4,8,5），它的最长上升子序列为（2,3,4,5），但如果
限制一定要包含第 2 个元素，那么满足此要求的最长上升子序列就只能是（2,7,8）了。
题目解析：
可以在 k 之前跑一遍最长上升子序列，去掉大于 k 的，然后在 k 后面跑一遍，去掉小于 k 的。当然也可以把这两步合并，见代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
#define ll long long
ll read(){
    ll q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')
        q=(ll)q*10+(ll)(ch-'0'),ch=getchar();
    return q;
}
int n,m,tot,bj=-1;
ll a[200005],b[200005];
int main()
{
    int i,j,kl;
    n=read();m=read();
    for(i=1;i<=n;i++)a[i]=read();
    for(i=1;i<=n;i++){
        kl=lower_bound(b+1,b+1+tot,a[i])-b;
        if(kl>tot)tot++;
        if(kl<=bj)continue;b[kl]=a[i];
        if(i==m){tot=kl;bj=kl;}
    }
    printf("%d",tot);
    return 0;
}
C++
Copy

T4

最短回文串

题目描述：如果一个字符串正过来读和倒过来读是一样的，那么这个字符串就被称作回文串。例如
abcdcba，abcddbca 就是回文串，而 abcdabcd 不是。
你要解决的问题是：对于任意一个字符串，输出将这个字符串变为回文串需要插入的最
少字符个数，比如，ab3bd 只需要插入 2 个字符就可以变为一个回文串
题目分析：用 f(i,j) 表示从 i 到 j 的字符串变成回文串的最少改变次数，那么如果 a[i]==a[j]，则 f(i,j)=f(i+1,j-1);
如果不等于的话，可以往左边加一个字母或者往右边加一个字母则：f(i,j)=min(f(i,j-1),f(i+1,j));
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
int n,f[5005][5005];char a[5005];
int main()
{
    int i,j,t;
    scanf("%d\n%s",&n,a);
    for(i=n;i>=1;i--)
        for(j=i+1;j<=n;j++){
        if(a[i-1]==a[j-1])f[i][j]=f[i+1][j-1];
        else f[i][j]=min(f[i+1][j],f[i][j-1])+1;
    }
    printf("%d",f[1][n]);
    return 0;
}
C++
Copy

现在我们回到标题，题目都很简单是吧，那么动规 5 是怎么挂的呢？
大约是蠢吧。

分类： 文章

litble

苟...苟活者在淡红的血色中，会依稀看见微茫的希望

0 条评论

发表回复

Avatar placeholder

您的邮箱地址不会被公开。 必填项已用 * 标注