XTYZ-NOIP+班刷题计划chapter4

箬蒻终于要动笔了。

第四章写的很慢因为，区间DP实在玩不转，好好加油⑧。

A - Grazing on the Run

题意：http://poj.org/problem?id=3042

可以想到当前吃掉的草一定是一个区间（因为经过的草一定会吃掉），然后最后一定会停在左端点或者右端点。
dp[ i ][ j ][0/1]表示已经吃了[ i , j ]的草，最后停在左/右端点时草的总腐败量，

在最左侧要到达i点可以通过i+1点或j点转移，在最右侧类似

转移到i时,除了即将到达的i点，还有未到达的(n-(j-i+1))个点，

即总共(n-(j-i))个点，它们的枯萎指数均在增加。

ps:做这题也发现memset一个赋最大值应用，但是还不是太懂为什么，先码着

memset(a,127,sizeof(a))，即得到无穷大。memset(a,128,sizeof(a))，即得到无穷小，与上述的值互为相反数。

对于a数组为int或long long时，成立。

#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
const int INF=0x3f3f3f;
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int p[1111];
int dp[1111][1111][2];
int main()
{
    int n,l;
    while(~s2(n,l))
    {
        for(int i=1;i<=n;s1(p[i++]));
        sort(p+1,p+n+1);
        mem(dp,127);
        for(int i=1;i<=n;i++)
            dp[i][i][0]=dp[i][i][1]=abs(l-p[i])*n;//走到i点过程中有n个点正在腐化
        for(int len=2;len<=n;len++)
        {
            for(int i=1;i<=n-len+1;i++)
            {
                int j=i+len-1;
                dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(n-(j-i))*abs(p[i+1]-p[i]));
                dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(n-(j-i))*abs(p[j]-p[i]));
                dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(n-(j-i))*abs(p[j]-p[j-1]));
                dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(n-(j-i))*abs(p[j]-p[i]));
            }
        }
        printf("%d\n",min(dp[1][n][0],dp[1][n][1]));
    };
    return 0;
}

E - Cow Relays

题意：http://poj.org/problem?id=3613

就是求S到E经过K个边的最短路啦）

主要用到的就是离散数学里的矩阵幂乘求可达性矩阵（结合Floyd思想）以及快速幂思想

一行Floyd算法：

c[i][j]=min(c[i][j],a[i][k]+b[k][j]);

求出的新矩阵c,矩阵里每条边都相当于从a中取出一条边（i，k），从b中取出一条边（k，j）组成新边，与矩阵幂乘相同，

求出的c中即为原图中每个点经过两条边到达其他点的最小距离，要求经过K条边的最短路，做K-1次矩阵幂乘即可。

同时，如果每次都和原图矩阵相乘太费时间，采用快速幂的思想，将K拆为1+x(K为奇数时)和x+x。

同时发现和A题相同有memset赋最值的应用，但是不知为何赋值127会WA。。。以后还是赋0x3f保险吧。。。

AC代码：

#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
const int INF=0x3f3f3f;
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int K,T,S,E,n;
int mp[1111];
struct IN
{
    int a[222][222];
    IN operator * (IN &b)
    {
        IN c;
        mem(c.a,0x3f);
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    c.a[i][j]=min(c.a[i][j],a[i][k]+b.a[k][j]);
        return c;
    }
}st,ans;
void solve()
{
    ans=st;
    K--;
    while(K)
    {
        if(K&1) ans=ans*st;
        st=st*st;
        K>>=1;
    }
}
int main()
{
    n=0;
    mem(st.a,0x3f);mem(mp,0);
    scanf("%d %d %d %d",&K,&T,&S,&E);
    for(int i=0,u,v,w;i<T;i++)
    {
        s3(w,u,v);
        if(!mp[u]) mp[u]=++n;
        if(!mp[v]) mp[v]=++n;
        st.a[mp[u]][mp[v]]=st.a[mp[v]][mp[u]]=w;
    }
    solve();
    printf("%d\n",ans.a[mp[S]][mp[E]]);
    return 0;
}

K - Moogle

题意：http://poj.org/problem?id=3638

给你一个地图，有h个点但是只能保存c个点，未保存的点按照线性关系推算，问你这种推算方式最小误差是多少

又是DP。。dp[ i ][ j ]表示到i位置保存j 个房子的最小误差，

那么每个状态可由前面的状态推出（前面保存了j-1个房子的状态的dp值+前面状态末位置到现位置的总误差）

#include<cmath>

	#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
const int INF=0x3f3f3f;
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))



	double p[222];
double d[222][222];//只确定i,j，中间产生的总误差
double dp[222][222];
int main()
{
    int t;s1(t);
    while(t--)
    {
        int h,c;
        s2(h,c);
        mem(d,0);
        for(int i=1;i<=h;i++)
            scanf("%lf",&p[i]);
        for(int i=1;i<=h;i++)
        {
            for(int j=i+1;j<=h;j++)
            {
                double temp=(p[j]-p[i])/(j-i);
                for(int k=i+1;k<j;k++)
                    d[i][j]+=fabs(p[i]+temp*(k-i)-p[k]);
            }
        }
        //dp[i][j]表示在第i位置确定j个house
        mem(dp,0x43);
        for(int i=2;i<=h;i++)
        {
            dp[i][2]=d[1][i];
            for(int j=3;j<=c&&j<=i;j++)
            {
                for(int k=j-1;k<i;k++)//保存j-1个房子最少需要到j-1位置
                    dp[i][j]=min(dp[i][j],dp[k][j-1]+d[k][i]);
            }
        }
        printf("%.4lf\n",dp[h][c]/h);
    }
    return 0;
}

J - Evacuation

朕乏了

题意：http://poj.org/problem?id=3057

每个人不能同时出出口，但是可以走在同一块空地上

问你最小获救时间


	#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
const int INF=0x3f3f3f;
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
//二分图最大匹配匈牙利算法
//bfs预处理
int X,Y,n;
char mp[20][20];
//匈牙利
int vis[55555];
int match[55555];
vector<int>G[55555];
//建图
vector<int>dx,dy;//门的坐标
vector<int>px,py;//人的坐标
int dxx[5]={0,1,0,-1};
int dyy[5]={1,0,-1,0};
int dis[20][20][20][20];//前两维代表门后两维代表人



	void bfs(int x,int y,int d[20][20])//求出各点到每个门的距离
{
    queue<int>qx,qy;
    d[x][y]=0;
    qx.push(x);
    qy.push(y);
    while(!qx.empty())
    {
        x=qx.front();qx.pop();
        y=qy.front();qy.pop();
        for(int i=0;i<4;i++)
        {
            int nx=x+dxx[i],ny=y+dyy[i];
            if(nx>=0&&nx<X&&ny>=0&&ny<Y&&mp[nx][ny]=='.'&&d[nx][ny]<0)
            {
                d[nx][ny]=d[x][y]+1;
                qx.push(nx);
                qy.push(ny);
            }
        }
    }
}
void input()//输入加预处理
{
    s2(X,Y);
    dx.clear();dy.clear();
    px.clear();py.clear();
    mem(dis,-1);
    for(int i=0;i<X;i++)
        scanf("%s",mp[i]);
    for(int i=0;i<X;i++)
    {
        for(int j=0;j<Y;j++)
        {
            if(mp[i][j]=='D')
            {
                dx.push_back(i);
                dy.push_back(j);
                bfs(i,j,dis[i][j]);//相当于将四维数组的后两维传入函数



	}
            else if(mp[i][j]=='.')
            {
                px.push_back(i);
                py.push_back(j);
            }
        }
    }
}
int dfs(int v)
{
    vis[v]=1;
    int len=G[v].size();
    for(int i=0;i<len;i++)
    {
        int u=G[v][i];
        if(match[u]==-1||(!vis[match[u]]&&dfs(match[u])))
        {
            match[v]=u;
            match[u]=v;
            return 1;
        }
    }
    return 0;
}
int main()
{
    int t;s1(t);
    while(t--)
    {
        input();
        //建图
        n=X*Y;//时间上限
        int d=dx.size(),p=px.size();
        for(int i=0;i<n*d+p;i++) G[i].clear();
        for(int i=0;i<d;i++)
        {
            for(int j=0;j<p;j++)
            {
                if(dis[dx[i]][dy[i]][px[j]][py[j]]>=0)
                {
                    for(int k=dis[dx[i]][dy[i]][px[j]][py[j]];k<=n;k++)//将时间和门和人建边
                    {
                        int u=(k-1)*d+i,v=n*d+j;
                        //u相当于时间和门组成的二元组,i最大值就是d,所以乘d后加i(状压
                        //v即为此时的人，
                        //加n*d为了防止人编号和状压后的数字重合((k-1)*d+i小于n*d,所以n*d+j绝对大于(k-1)*d+i
                        //菊苣是怎么想到这样压缩状态的我哭了
                        G[u].push_back(v);
                        G[v].push_back(u);//二元组建边
                    }
                }
            }
        }
        //匈牙利找增广路
        int flag=0;
        if(p==0)
        {
            printf("0\n");
            continue;
        }
        int num=0;
        mem(match,-1);
        for(int i=0;i<n*d;i++)
        {
            mem(vis,0);
            if(dfs(i))
            {
                if(++num==p)//当匹配数到达总人数就说明可以在时间t内全部逃出了 {
                    printf("%d\n",i/d+1);
                    flag=1;
                    break;
                }
            }
        }
        if(flag==0) printf("impossible\n");
    }
    return 0;
}

F - Big Christmas Tree

题意：http://poj.org/problem?id=3013

给你每个点的权重和一些边，求以1点为根节点的最小树（边的价值之和最小）

圣诞树的边 u-v 的价值等于边 u-v 的权值*（v为根节点的子树中的所有节点的权重和）

超像最小生成树对吧，，，但是写到一半你会发现，这个价值计算方法，在得知最小树之前，是不能先算出每个边的价值的。。。

然后，

其实对于一个节点，它在走到根节点所经过的每一条路，都需要乘上这个节点的权值。因为这个节点是它所路过节点的子节点，

所以所有路过的边都会成上这个节点的权值。因为一个节点的权值是定值。

所以最后转换成求每个点到1点的最短路问题，，SPFA

n=0或者1，答案是0,V=1的时候，只有1一个节点，不需要任何边去构成

还有就是INF尽量大一些。


	//#include <bits/stdc++.h>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=5e4+10;
#define pi    acos(-1.0)
#define INF 0x3f3f3f3f3f
#define mod   1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)



	int n,m,tot;
int head[MAXN];
int w[MAXN];
ll dis[MAXN];
int vis[MAXN];
struct IN
{
    int v;
    ll val;
    int next;
}edge[MAXN<<2];//注意无向存图
void addedge(int u,int v,ll val)
{
    edge[tot].v=v;
    edge[tot].val=val;
    edge[tot].next=head[u];
    head[u]=tot++;
}
void input()
{
    s2(n,m);
    tot=1;
    mem(head,0);
    for(int i=1;i<=n;i++)
    {
        vis[i]=0;
        dis[i]=INF;
    }
    for(int i=1;i<=n;i++)
        s1(w[i]);
    for(int i=0;i<m;i++)
    {
        int u,v;
        ll val;
        scanf("%d %d %lld",&u,&v,&val);
        addedge(u,v,val);
        addedge(v,u,val);
    }
}
void spfa_bfs(int x)//x=start
{
    queue<int>q;
    q.push(x);
    vis[x]=1;dis[x]=0;
    while(!q.empty())
    {
        x=q.front();q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=edge[i].next)
        {
            int nx=edge[i].v;
            if(dis[nx]>dis[x]+edge[i].val)
            {
                dis[nx]=dis[x]+edge[i].val;
                if(!vis[nx])
                {
                    vis[nx]=1;
                    q.push(nx);
                }
            }
        }
    }
}
int main()
{
    int t;s1(t);
    while(t--)
    {
        input();
        if(n==0||n==1) printf("0\n");
        else
        {
            spfa_bfs(1);
            ll ans=0;
            int flag=1;
            for(int i=1;i<=n;i++)
            {
                if(dis[i]<INF)
                    ans+=w[i]*dis[i];
                else
                {
                    printf("No Answer\n");
                    flag=0;
                    break;
                }
            }
            if(flag) printf("%lld\n",ans);
        }
    }
    return 0;
}

XTYZ-NOIP+班刷题计划chapter4

A - Grazing on the Run

E - Cow Relays

K - Moogle

J - Evacuation

F - Big Christmas Tree