不想多说什么,再次错过一次AK机会

T1 青蛙的烦恼

蛤の烦恼
⃢ — ⃢
设$f(i,j,k)$为在区间$[l,r]$内,位置为k时遍历所有坐标的最短路径。
$dis(i,j)$表示从点i到点j的距离
这样空间复杂度为$n^3$,1e9无法接受
不难发现k只可能为i或者为j
所以设$f(i,j,t)$为当前位置为i,区间长度为j。t=0表示区间在i右边,t=1表示区间在左边。
空间复杂度降到了$n^2$
于是就轻松解决了

代码:

#include <bits/stdc++.h>
#define dis(a,b) (sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])))
using namespace std;
int n;
double x[1000],y[1000],f[1000][1000][2];
bool book[1000][1000][2];
double dfs(int cur,int l,int t)
{
    if(book[cur][l][t])return f[cur][l][t];
    book[cur][l][t]=1;
    if(l==1)return 0;
    if(!t)
        f[cur][l][t]=
            min(dfs(cur+l-1,l-1,1)+dis(cur,cur+l-1),dfs(cur+1,l-1,0)+dis(cur,cur+1));
    else
        f[cur][l][t]=
            min(dfs(cur-l+1,l-1,0)+dis(cur,cur-l+1),dfs(cur-1,l-1,1)+dis(cur,cur-1));
    return f[cur][l][t];
}
int main()
{
    freopen("frog.in","r",stdin),freopen("frog.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
    printf("%.3f\n",dfs(1,n,0));
    return 0;
}

T2 警卫安排

我真是太弱了
没事多叉转二叉干啥
转二叉理论上也能做,只是需要讨论4种情况。
所以不如不转



//以上截图自ppt
下面代码中,0表示安排警卫,1表示被父亲看到,2表示被儿子看到。
代码:

#include <bits/stdc++.h>
using namespace std;
int n,v[1000],root,f[1000][3];
bool book[1000];
vector<int> g[1000];
int dfs(int u,int w)
{
    if(f[u][w]!=-1)return f[u][w];
    switch(f[u][w]=0,w)
    {
        case 0:
            for(int i=0;i<g[u].size();i++)
                f[u][w]+=min(dfs(g[u][i],0),min(dfs(g[u][i],1),dfs(g[u][i],2)));
            f[u][w]+=v[u];break;
        case 1:
            for(int i=0;i<g[u].size();i++)f[u][w]+=min(dfs(g[u][i],0),dfs(g[u][i],2));
            break;
        case 2:
            f[u][w]=1e8;
            for(int i=0;i<g[u].size();i++)
                f[u][w]=min(f[u][w],dfs(g[u][i],0)-min(dfs(g[u][i],0),dfs(g[u][i],2)));
            for(int i=0;i<g[u].size();i++)
                f[u][w]+=min(dfs(g[u][i],0),dfs(g[u][i],2));
        break;
    }
    return f[u][w];
}
int main()
{
    freopen("security.in","r",stdin),freopen("security.out","w",stdout);
    scanf("%d",&n);
    for(int i=1,j,k;i<=n;i++)
    {
        scanf("%d",&j),scanf("%d%d",&v[j],&k);
        for(int i1=1,j1;i1<=k;i1++)scanf("%d",&j1),g[j].push_back(j1),book[j1]=1;
    }
    for(int i=1;i<=n;i++)if(!book[i]){root=i;break;}
    memset(f,-1,sizeof(f)),printf("%d\n",min(dfs(root,0),dfs(root,2)));
    return 0;
}

T3 最长上升子序列

最水的一题。
在1…k跑一遍lis,再再k+1…n跑一遍lis即可。
第二次跑lis的时候需要筛掉所有小于第k个数的元素
答案为$f[k]+max\{f[k+1…n]\}$
也可以一开始先筛掉所有小于第k个数的元素,再跑一遍lis
需要用nlogn的算法

代码:

#include <bits/stdc++.h>
using namespace std;
int n,k,a[200005],e[200005],cnt,f[200005],ans;
int main()
{
    freopen("lis.in","r",stdin),freopen("lis.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=k;i++)
    {
        f[i]=(int)(lower_bound(e+1,e+1+cnt,a[i])-e);
        if(f[i]>cnt)e[++cnt]=a[i];else if(a[i]<e[f[i]])e[f[i]]=a[i];
    }
    memset(e,0,sizeof(e)),cnt=0;
    for(int i=k+1;i<=n;i++)
        if(a[i]>a[k])
        {
            f[i]=(int)(lower_bound(e+1,e+1+cnt,a[i])-e);
            if(f[i]>cnt)e[++cnt]=a[i];else if(a[i]<e[f[i]])e[f[i]]=a[i];
            ans=max(ans,f[i]);
        }
    printf("%d\n",ans+f[k]);
    return 0;
}

T4 最短回文串

区间dp
设$f(i,j)$为把$[i,j]$这段子串变为一个回文串的最小代价
当$s[i]==s[j]$时$f(i,j)=f(i+1,j-1)$
否则$f(i,j)=min\{f(i+1,j),f(i,j-1)\}+1$

代码:

#include <bits/stdc++.h>
using namespace std;
int n,f[5005][5005];
char s[5005];
int main()
{
    freopen("palindrome.in","r",stdin),freopen("palindrome.out","w",stdout);
    scanf("%d%s",&n,s);
    for(int l=1;l<n;l++)
        for(int i=0;i+l<n;i++)
        {
            f[i][i+l]=min(f[i+1][i+l],f[i][i+l-1])+1;
            if(s[i]==s[i+l])f[i][i+l]=min(f[i][i+l],f[i+1][i+l-1]);
        }
    printf("%d\n",f[0][n-1]);
    return 0;
}

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

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

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

你是机器人吗? =。= *