day4：选拔赛3 && 简单动态规划

超、凢脫俗 2021-10-30 02:50 231阅读 0赞

# day4：选拔赛3 && 简单动态规划 #

既然热爱，那就坚持，昨天偷懒去了，今天把昨天的总结补上

上午还是照常的听课，开始以为是简单DP，觉得会挺简单的（仿佛有点骄傲…），然而发现自己原来就只会拿几道简单的模板题，例如：数塔，0-1背包（裸的），最长上升子序列，最长公共子序列

但是遇到稍微变形就不会了，就拿选拔赛1的D题，一道几乎是裸的LIS的题，居然没做出来，心塞…

虽然上午感觉懂了不少，但是做起题来，却是一塌糊涂，

--------------------

## 2019ACM集训基础动态规划一 ##

--------------------

A题：[hdu 2069：Coin Change ][hdu 2069_Coin Change]

一道基本上是上课的原题，稍微难点的就是并不是求出最少需要硬币的个数，而是求总共有多少种方案可以满足硬币所表示的面值总和为题目所给数据

但是还是磕磕碰碰了好久才A出来。。。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define ll long long
    using namespace std;
    int value[5]={
        1,5,10,25,50};
    ll dp[255][110];           //dp[j][k]:用k个硬币组成j金额的个数
    int main()
    {
        
        int n;
        while(~scanf("%d",&n))
        {
        
            memset(dp,0,sizeof(dp));
            dp[0][0]=1;
            for(int i=0;i<5;i++)
            {
        
                for(int k=1;k<=100;k++)
                {
        
                    for(int j=value[i];j<=n;j++)
                    {
        
                        dp[j][k]+=dp[j-value[i]][k-1];
                    }
                }
            }
            int ans=0;
            for(int i=0;i<=100;i++)
                ans+=dp[n][i];
            printf("%d\n",ans);
        }
        return 0;
    }

B题：[hdu 1257：最少拦截系统][hdu 1257]

一道令我悲伤的题

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int f[100010];
    int a[100010];
    int main()
    {
        
        int n;
        while(~scanf("%d",&n))
        {
        
            int num=0;
            memset(a,0,sizeof(a));
            memset(f,0,sizeof(f));
            for(int i=1;i<=n;i++)
            {
        
                scanf("%d",&a[i]);
                f[i]=1;
            }
            for(int i=1;i<=n;i++)
            {
        
                for(int j=1;j<=i;j++)
                {
        
                    if(a[j]<a[i])
                        f[i]=max(f[i],f[j]+1);
                }
            }
            for(int i=1;i<=n;i++)
            {
        
                num=max(num,f[i]);
            }
            printf("%d\n",num);
        }
        return 0;
    }

C题：[hdu 1024：Max Sum Plus Plus][hdu 1024_Max Sum Plus Plus]

求最大M字段和

开始完全没思路，虽然感觉就是一个简单的一维DP，但是就是不知道怎么做，最后也是看题解才明白

直接就是这样一个简单的状态转移方程：

**dp\[i\]\[j\]=max(dp\[i\]\[j-1\]+a\[j\],max(dp\[i-1\]\[k\])+a\[j\])**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    const int inf=0xffffff0;
    const int maxn=1000010;
    int dp[maxn];
    int Max[maxn];
    int a[maxn];
    int main()
    {
        
        int n,m;
        while(~scanf("%d%d",&m,&n))
        {
        
            memset(a,0,sizeof(a));
            memset(dp,0,sizeof(dp));
            memset(Max,0,sizeof(Max));
            for(int i=1;i<=n;i++)
                scanf("%d",&a[i]);
            int mmax;
            for(int i=1;i<=m;i++)
            {
        
                mmax=-inf;
                for(int j=i;j<=n;j++)
                {
        
                    dp[j]=max(dp[j-1]+a[j],Max[j-1]+a[j]);
                    Max[j-1]=mmax;
                    mmax=max(mmax,dp[j]);
                }
            }
            printf("%d\n",mmax);
        }
    }

E题：[hdu 1864：最大报销额][hdu 1864]

哎，又犯了老毛病了，一开始又觉得贪心就可以了，这不就是一个**0-1背包**吗

但是还是没做出来，最后看题解，补的题

0-1背包算法中都是整数，但是这里有实数，所有就有点难处理，但是看博客时，发现大佬用实数直接乘以100，然后就变成整数了，这也是一门艺术啊（aaaa）  
这个解决之后，然后基本上问题就游刃而解了

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int dp[3001000];
    int main()
    {
        
        double Q;
        int n,m;
        while(~scanf("%lf%d",&Q,&n))
        {
        
            if(n==0)
                break;
            memset(dp,0,sizeof(dp));
            int aa[35];
            int q=(int)(Q*100);
            int t=1;
            for(int i=0;i<n;i++)
            {
        
                double price;
                char type;
                int num;
                int m;
                int a=0,b=0,c=0;
                int flag=0;
                scanf("%d",&m);
                for(int j=0;j<m;j++)
                {
        
                    char str[100];
                    scanf("%s",str);
                    sscanf(str,"%c:%lf",&type,&price);       //比较高级的操作，这个必须得记住，以后遇到就方便多了
                    //cout<<price<<endl;
                    num=(int)(price*100);
                    if(type=='A')
                    {
        
                        a+=num;
                    }
                    else if(type=='B')
                        b+=num;
                    else if(type=='C')
                        c+=num;
                    else
                    {
        
                        flag=1;
                    }
                    if(a+b+c>100000||a>60000||b>60000||c>60000)
                        flag=1;
                }
                if(flag==0)
                {
        
                    aa[t++]=a+b+c;
                }
            }
            for(int i=1;i<t;i++)
            {
        
                for(int j=q;j>=1;j--)
                {
        
                    if(j>=aa[i])
                    {
        
                        dp[j]=max(dp[j],dp[j-aa[i]]+aa[i]);
                    }
                }
            }
            printf("%.2f\n",dp[q]/100.00);
        }
        return 0;
    }

K题：[hdu 1003：Max Sum][hdu 1003_Max Sum]

求最长子串，使得其和最大

如果只求和，那肯定好简单了，但是这稍微高级了点，还要求对应的起终点

还是没有很快的想到怎么做 ，其实好像就是一个基本的一维dp

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int a[100010];
    int main()
    {
        
        int t;
        int n;
        scanf("%d",&t);
        for(int k=1;k<=t;k++)
        {
        
            scanf("%d",&n);
            memset(a,0,sizeof(a));
            for(int i=1;i<=n;i++)
            {
        
                scanf("%d",&a[i]);
            }
            int ThisSum=0,LastSum=0;
            int s=1,e=1;
            int ss=1,ee=1;
            int mmax=-1000;
            for(int i=1;i<=n;i++)
            {
        
                if(LastSum>=0)
                {
        
                    ThisSum=LastSum+a[i];
                    e=i;
                }
                else
                {
        
                    ThisSum=a[i];
                    s=i;
                    e=i;
                }
                if(mmax<=ThisSum)
                {
        
                    mmax=ThisSum;
                    ss=s;
                    ee=e;
                }
                LastSum=ThisSum;
            }
            printf("Case %d:\n",k);
            printf("%d %d %d\n",mmax,ss,ee);
            if(k<t)
                printf("\n");
        }
        return 0;
    }

又有好多题没补，估计其余题，又不知道是哪一次遇到后，又后悔现在没补，导致又不会做，

dp太难了（哭辽），状态转移方程完全不知道该往哪个方向找

感觉还是题做的太少了，以后要加强这方面练习，

下午又是苦逼的选拔赛，四个小时做出来两道题，心态崩了，全是一些找规律题，气人的是：有一道题，其实我已经找出规律了，但是特判了下，一直WA。。。。。

--------------------

## 选拔赛3 ##

--------------------

B题：[hdu 4902：Nice boat][hdu 4902_Nice boat]

知道是一道线段树的题，但是还是尝试了下暴力，想着万一A了呢，但是不出意外，还是TLE了

但是线段树又不知道该怎么区间修改，感觉这样的话，时间复杂度也低不了多少啊。

这题有必要找时间补补

D题：[hdu 4882：ZCC Loves Codefires][hdu 4882_ZCC Loves Codefires]

一道贪心的简单题，但是比赛的时候就是找不到贪心的方向，导致很遗憾，没做出来

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    using namespace std;
    struct node
    {
        
        int Ei;
        int Ki;
    } a[100010];
    bool cmp(node x,node y)
    {
        
        return x.Ki*y.Ei>y.Ki*x.Ei;
    }
    int main()
    {
        
        int n;
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        for(int i=0; i<n; i++)
            scanf("%d",&a[i].Ei);
        for(int i=0; i<n; i++)
            scanf("%d",&a[i].Ki);
        sort(a,a+n,cmp);
        ll time=0;
        ll sum=0;
        for(int i=0; i<n; i++)
        {
        
            time+=a[i].Ei;
            sum+=a[i].Ki*time;
        }
        printf("%lld\n",sum);
        return 0;
    }

G题：[hdu 5366：The mook jong][hdu 5366_The mook jong]

好，坑爹的找规律题来了，显然我没找到，疯狂打表最终还是没找到规律

原来就是一个坑爹的  
f\[i\]=f\[i-1\]+f\[i-3\]+1

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    using namespace std;
    int main()
    {
        
        ll f[65];
        int t=0;
        f[1]=1;
        f[2]=2;
        f[3]=3;
        int cnt=6;
        for(int i=4;i<=60;i++)
        {
        
            f[i]=f[i-1]+f[i-3]+1;
        }
        int n;
        while(~scanf("%d",&n))
        {
        
            printf("%lld\n",f[n]);
        }
        return 0;
    }

H题：[hdu 5158：Have meal][hdu 5158_Have meal]

这场选拔赛，可能我唯一的看点就是这个是首A，但是其实这题就是一道大水题

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int main()
    {
        
        int n,m;
        int num;
        while(~scanf("%d%d",&n,&m))
        {
        
            if(n>=m)
            {
        
                printf("%d\n",m-1);
            }
            else
            {
        
                num=m%n;
                if(num==0)
                    printf("%d\n",n-1);
                else
                    printf("%d\n",num-1);
            }
        }
        return 0;
    }

I题：[hdu 5703：Desert][hdu 5703_Desert]

又是一道大水题，也是我做出来的最后一题，

J题：[hdu 4861：Couple doubi][hdu 4861_Couple doubi]

这题是最可惜的，好不容易找到规律，但是由于自己想多了，导致一直WA

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int main()
    {
        
        int k,p;
        while(~scanf("%d%d",&k,&p))
        {
        
            if((k/(p-1)%2==0))
                printf("NO\n");
            else
                printf("YES\n");
        }
        return 0;
    }

这些题目感觉应该是得做出来的，四个小时做两道题，心态都崩了

[hdu 2069_Coin Change]: http://acm.hdu.edu.cn/showproblem.php?pid=2069
[hdu 1257]: http://acm.hdu.edu.cn/showproblem.php?pid=1257
[hdu 1024_Max Sum Plus Plus]: http://acm.hdu.edu.cn/showproblem.php?pid=1024
[hdu 1864]: http://acm.hdu.edu.cn/showproblem.php?pid=1864
[hdu 1003_Max Sum]: http://acm.hdu.edu.cn/showproblem.php?pid=1003
[hdu 4902_Nice boat]: http://acm.hdu.edu.cn/showproblem.php?pid=4902
[hdu 4882_ZCC Loves Codefires]: http://acm.hdu.edu.cn/showproblem.php?pid=4882
[hdu 5366_The mook jong]: http://acm.hdu.edu.cn/showproblem.php?pid=5366
[hdu 5158_Have meal]: http://acm.hdu.edu.cn/showproblem.php?pid=5158
[hdu 5703_Desert]: http://acm.hdu.edu.cn/showproblem.php?pid=5703
[hdu 4861_Couple doubi]: http://acm.hdu.edu.cn/showproblem.php?pid=4861