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;
}

T2

警卫安排

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

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;
}

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;
}

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


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

litble

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *