exercise6

终于考完了…又开始康复训练了，

纯菜，发现很多东西去年会写的今年已经不会了，我完蛋了
算了，写点东西下来吧
依然在看雨巨的算法入门课
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊我怎么还在入门啊

花店橱窗

传送门：花店橱窗
题意自己看去吧
线性dp+还原
$f[i] [j]$表示第i个花放在j花瓶的最大美观程度，但是必须知道第i-1个花放在了哪里，才能推出i的情况，怎么做呢，暴力枚举吧：
从第一个花瓶开始向后，当前f[i] [j]的值为：i-1朵花放在k且第i朵放在j时的最大值（注意判断边界条件）
状态转移：$f[i] [j]=max(f[i-1] [k]+a[i] [j],f[i] [j])$
答案就是扫一遍最后一行，取一个最大值
还原方法：按照dp倒退回去就行
贴个代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,t,a[N][N],f,v,b[N][N],inf=0x3f3f3f3f;
int re[N];
int main()
{
    cin>>f>>v;
    int ans=-1*inf;
    memset(b,-1*inf,sizeof(b));
    for(int i=1;i<=f;i++)
        for(int j=1;j<=v;j++)
            cin>>a[i][j];
    for (int i=1;i<=v;i++) 
    {
        b[1][i] = a[1][i];
    }
    for(int i=1;i<=f;i++)
        for(int j=i;j<=v-(f-i);j++)
            for(int k=i-1;k<=j-1;k++)
                b[i][j]=max(b[i-1][k]+a[i][j],b[i][j]);
        for(int i=1;i<=v;i++)
            ans=max(ans,b[f][i]);
    int reans=ans;
    for(int i=f;i>=1;i--)
        for(int j=1;j<=v;j++)
        {
            if(b[i][j]==reans)
            {
                re[i]=j;
                reans-=a[i][j];break;
            }
        }
    cout<<ans<<endl;
    for(int i=1;i<=f;i++)
    {
        cout<<re[i]<<" ";
    }
}

传球游戏

传送门：传球游戏
这题就是一个很简单的线性dp，状态转移方程很好想，因为每次只能传给左右两边，所以就讲上一次在左边的情况加上上一次在右边的情况即可。
dp[i] [j]为第i次传球在j手上的方法数
需要注意的是，所有人是一个圈，所以还需要mod一下，用0表示n

#include<bits/stdc++.h>
using namespace std;
const int N=50;
int n,m,dp[N][N];//第i次传球在j手上的答案
int main()
{
    cin>>n>>m;
    dp[1][2]=1;dp[1][0]=1;
    for(int i=2;i<=m;i++)
    {
        for(int j=0;j<n;j++)
        {
            dp[i][j]=dp[i-1][(j-1+n)%n]+dp[i-1][(j+1)%n];
        }
    }
    cout<<dp[m][1]<<endl;
}

合唱队列

传送门：合唱队列
最长上升子序列问题，从左到右算一遍，再从右到左算一遍最长下降子序列，以i为分界，左边的最大上升子序列+右边的最大下降子序列，因为都包含i，所以要减一

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int n,a[N],d[N],p[N];//以i为中点 j为必须包含数
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    d[1]=1,p[n]=1;//zeng
    for(int i=1;i<=n;i++)
    {
        int mmax=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i]) mmax=max(d[j]+1,mmax);
        }
        d[i]=mmax;
    }
    for(int i=n;i>0;i--)
    {
        int mmax=1;
        for(int j=n;j>i;j--)
        {
            if(a[j]<a[i]) mmax=max(p[j]+1,mmax);
        }
        p[i]=mmax;
    }
    int mmax=1;
    for(int i=1;i<=n;i++)
    {
        //cout<<d[i]<<" "<<p[i]<<endl;
        mmax=max(d[i]+p[i]-1,mmax);
    }
    cout<<n-mmax<<endl;
}

拦截导弹

传送门：拦截导弹

这题很好看出第一问是一个最长不上升子序列，但是第二问还挺难想的
贴一个我觉得讲的很好的题解点击
这题卡了一下LIS的时间复杂度，dp的方法是$O(n^2)$,用dp+贪心+二分只要$O(nlogn)$
都贴一下代码吧

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n=1,a[N],d[N],p[N];
int main()
{
    while(cin>>a[n])
    {
        n++;
    }n--;
    int mmmax=1,mmmax2=1;
    for(int i=1;i<=n;i++)
    {
        int mmax=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]>a[i]) mmax=max(d[j]+1,mmax);
        }
        d[i]=mmax;
        mmmax=max(mmmax,d[i]);
    }
    for(int i=1;i<=n;i++)
    {
        int mmax=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]<=a[i]) mmax=max(p[j]+1,mmax);
        }
        p[i]=mmax;
        mmmax2=max(mmmax2,p[i]);
    }
    cout<<mmmax<<endl;
    cout<<mmmax2<<endl;
}

第二种方法，具体解释那个帖子里也有

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n=1,a[N],d[N];
vector<int>vec;
int main()
{
    while(cin>>a[n])
    {
     n++;
 }n--;
    for(int i=1;i<=n;i++)
    {
        auto pos1=upper_bound(vec.begin(),vec.end(),a[i],greater<int>());
        if(pos1==vec.end()) vec.push_back(a[i]);
        else
        vec[pos1-vec.begin()]=a[i];
    }
    int nn=vec.size();
    cout<<nn<<endl;
    vec.clear();
    for(int i=1;i<=n;i++)
    {
        auto pos1=lower_bound(vec.begin(),vec.end(),a[i]);
        if(pos1==vec.end()) vec.push_back(a[i]);
        else
        vec[pos1-vec.begin()]=a[i];
    }
    nn=vec.size();
    cout<<nn<<endl;
}

数学考试

传送门：数学考试

这题我感觉…怎么说呢 感觉很暴力
先统计一下以i为起点，长度为k的字段和为多少
然后从左到右求一下以i为分割，左边的最大值
从右往左再求一下i右边的最大值
再遍历一遍，就得到答案了

后面看了一下别的题解，可以用前缀和优化一下（55555我又没想到，感觉这个挺好想的呀）
WA了几发在数据范围上…为什么我又不开longlong啊

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int t,n,k,a[N],d[N],l[N],r[N];
const int INF=-0x3f3f3f3f;
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        memset(d,INF,sizeof(d));
        memset(l,INF,sizeof(l));
        memset(r,INF,sizeof(r));
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            cnt+=a[i];
            if(i==k) d[i]=cnt;
            else if(i>k)
            {
                cnt-=a[i-k];
                d[i]=cnt;
            }
        }
        int maxl=-1e18,maxr=-1e18;
        for(int i=k;i<=(n-k);i++)
        {
            l[i]=max(l[i-1],d[i]);
        }
        for(int i=(n-k);i>=k;i--)
        {
            r[i]=max(r[i+1],d[i+k]);
        }
        int mm=-1e18;
        for(int i=k;i<=(n-k);i++)
        {
            mm=max(mm,l[i]+r[i]);
        }
        cout<<mm<<endl;
    }
}

小A买彩票

传送门：小A买彩票
…这题好像是之前天梯赛选拔一模一样的题目 好像当时dfs搜的还是干嘛的 没出的来
现在一看 这不还是简单dp吗 dp[i] [j]表示第i张彩票赚j元的情况
dp[i] [j]=dp[i-1] [j-1]+dp[i-1] [j-2]+dp[i-1] [j-3]+dp[i-1] [j-4]
特判需要注意下

#include<bits/stdc++.h>
using namespace std;
int n;
long long dp[35][150];
long long quickpow(long long a,long long p)
{
    long long res=1;
    while(p)
    {
        if(p&1) res=res*a;
        a=a*a;
        p>>=1;
    }
    return res;
}
int main()
{
    cin>>n;
    dp[1][1]=1;dp[1][2]=1;dp[1][3]=1;dp[1][4]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=i;j<=4*i;j++)
        {
            for(int k=1;k<=4;k++)
            {
                if(k<=j) dp[i][j]+=dp[i-1][j-k];
            }
        }
    }
    long long sum=0;
    //不亏本
    for(int i=3*n;i<=4*n;i++)
    sum+=dp[n][i];
    long long sumd;
    sumd=quickpow(4,n);
    long long g=__gcd(sum,sumd);
    sum/=g;
    sumd/=g;
    if (n==0) sum=1,sumd=1;
    printf("%lld/%lld\n",sum,sumd);
}

购物

传送门：购物

dp[i] [j]表示第i天买j东西的最少费用
首先要对每天的东西进行一个排序，要是一定要买2个糖，肯定买便宜的啊
用一个mai[i] [j]数组记录一下第i天买j个糖花的钱
转移方程：dp[i] [j]=min(dp[i] [j],dp[i-1] [k]+mai[i] [j-k]+(j-k)*(j-k))
k就是枚举的每天买的糖
注意一下边界条件 必须保证i天有i个糖
有点像那个花店橱窗 发现我每次到暴力的时候反而不知道怎么写了…

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=305;
int n,m,a[N][N],mai[N][N],dp[N][N];//第i天买j东西的最少费用
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    memset(dp,0x3f3f3f3f,sizeof(dp));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    for(int i=1;i<=n;i++)
    sort(a[i]+1,a[i]+1+m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            mai[i][j]=mai[i][j-1]+a[i][j];
        }
    for(int i=1;i<=m;i++)//第1天
        dp[1][i]=mai[1][i]+i*i;
    for(int i=2;i<=n;i++)
    {
        for(int j=i;j<=n;j++)//至少i个
        {
            for(int k=0;k<=j;k++)
            {
                if(j-k<=m)
                dp[i][j]=min(dp[i][j],dp[i-1][k]+mai[i][j-k]+(j-k)*(j-k));
            }
        }
    }
    cout<<dp[n][n];
}

采药

传送门：采药
其实感觉我对于背包问题的理解一直不是特别透彻，我会写题，但是感觉就是很钝，借这题梳理一遍。

这题就是经典的01背包问题
dp[i] [j]选前i个物品所占体积j的最大价值
两个状态：选第i个物品或者不选第i个物品，从i-1的状态转化过来。注意：如果没有办法舍弃原先的体积选择装入该物品（就是已用体积比w[i]小）还是要继承前面i-1的情况的。
先说一下这里的初始化有两种情况，如果题目问的是恰好最后体积为V，那么初始化就要设置为-INF，而如果不需要恰好，可以初始化为0，就好比一开始给每个位置占任意体积的空气一样。
贴个代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int t,m,v[N],w[N],dp[N][1005];//前i个花j时的最大价值
int main()
{
    cin>>t>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=t;j++)
        {
            if(j>=w[i])
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
            else
            dp[i][j]=dp[i-1][j];
        }
    cout<<dp[m][t]<<endl;
}

进一步可以优化空间复杂度
我们发现每一次i的更新只与i-1有关，那么其实不需要记录前面i-2甚至更远的数据，可以采用01滚动的方式，当然，其实直接降成一维的也可以，我们注意到，

失衡天平

传送门：失衡天平