欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2017.08.06【NOIP提高组】模拟赛B组总结

程序员文章站 2024-03-18 23:17:04
...

今天做的非常差,只有130分(人家都有AK的!!)
好吧20+100+10=130分。
T1:天平
http://172.16.0.132/senior/#contest/show/2068/0
比赛时候,我用dp做,很傻逼。结果答案错误……
其实,可以直接爆搜加一点剪枝。或者类似中途相遇法之类的……

#include<cstdio>
#include<iostream>
#define max(x,y) (((x)>(y))? x:y)
using namespace std;
int n,c;
long long f[41],v[41],x,ans;
void dg(int t,int s)
{
    if (s>c) return;
    if (s+f[t-1]<=c)
    {
        ans=max(s+f[t-1],ans);
        return; 
    }
    ans=max(ans,s);
    int i;
    for (i=1;i<t;++i)
        dg(i,s+v[i]);
}
int main()
{
    scanf("%d%d",&n,&c);
    int i,j,k;
    long long nn;
    for (i=1;i<=n;++i)
    { 
        scanf("%lld",&x);
        if (x<=c) 
        {
            v[i]=x;
            nn=i;
            f[i]=f[i-1]+x;
        }
    } 
    dg(nn+1,0);
    printf("%lld\n",ans);
}

T2:游历的路线(lines)
http://172.16.0.132/senior/#contest/show/2068/1
比赛时唯一A了的题,这是一道dp题,设f[i][j]表示第i天到达j地的最优值。
还有记录g[i][j][k]表示第i天,从第j个地方到第k个地方的费用。
直接o(1)调用就好了。

#include<cstdio>
#include<iostream>
#include<cstring>
#define min(x,y) (((x)<(y))? x:y)
using namespace std;
int g[201][101][101],f[201][101],n,m;
int main()
{
    freopen("lines.in","r",stdin);
    freopen("lines.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x,y,i,j,t,a[21],k,l;
    x=1;
    y=2;
    for (i=1;i<=n*(n-1);++i)
    {
        if (x==y) y++;
        if (y>n)
        {
            x++;
            y=1;
        }
        scanf("%d",&t);
        for (j=1;j<=t;++j)
            scanf("%d",&a[j]);
        for (j=1;j<=m;++j)
            g[j][x][y]=a[(j-1)%t+1];
        ++y;
    }
    memset(f,127,sizeof(f));
    for (i=1;i<=n;++i)
        f[1][i]=g[1][1][i];
    for (i=2;i<=m;++i)
    {
        for (j=1;j<=n;++j)
            for (k=1;k<=n;++k)
                if (j!=k&&g[i][k][j]>0&&f[i-1][k]>0)
                    f[i][j]=min(f[i][j],f[i-1][k]+g[i][k][j]);
    }
    if (f[m][n]==2139062143) printf("0\n");
    else printf("%d\n",f[m][n]);
}

T3:【NOI2015模拟8.17】最短路(shortest)
http://172.16.0.132/senior/#contest/show/2068/2
详见同作者的题解:http://blog.csdn.net/cdy1206473601/article/details/76777699