解题报告 P2858 [USACO06FEB]Treats for the Cows G/S

题目内容

P2858

大意:n 个元素的序列,每次可以从头或者尾去掉一个元素,获得的收益是这个元素的权值乘上该次去除的次数,求最大收益。

解题思路

不难发现,这题由于去除元素的顺序对最终的结果是有影响的,所以不能直接贪心,考虑使用 dp。

这题一眼看上去像是一个区间 dp,那我们先开始寻找如何定义状态。考虑我们已经去除了 [i,j] 以外的所有元素,可以发现外面元素去除的顺序已经不重要了,满足无后效性,说明可以这样定义状态:f_{i,j} 表示还剩 [i,j] 时可以达到的最大收益。

转移:当我们达到 [i,j] 时,要么是去掉了第 i-1 个元素,要么是去掉了第 j+1 个元素,设当前的天数为 d,第 i 个元素为 v_i,则有状态转移方程

f_{i,j}=\max(f_{i-1,j}+dv_{i-1},f_{i,j+1}+dv_{j+1})

那么枚举区间长度的时候就必须从大到小枚举,为了方便可以在枚举区间长度的同时枚举天数

最后统计答案的时候答案为 ans=\displaystyle\max_{i=1}^n\lbrace f_{i,i}+nv_i\rbrace,输出即可。

#include <cstdio>
#include <cctype>

//快读

//max

const int maxn=2005;
int v[maxn],f[maxn][maxn];

int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
        v[i]=read();
    for(int len=n-1,day=1;len>=1;len--,day++)//从n-1开始枚举区间长度
        for(int i=1,j=i+len-1;j<=n;i++,j++)
            f[i][j]=max(f[i][j+1]+v[j+1]*day,f[i-1][j]+v[i-1]*day);
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i][i]+n*v[i]);
    printf("%d\n",ans);
    return 0;
}

当然,这题正序枚举区间长度也是可以的,只是倒序的更好理解我太菜不会

2019 CSP-J 题解

前言

咕咕咕了好久,终于今天把 T3 的坑给补回来了,于是打算写一波题解。

勿吐槽码风,丑是必然的,毕竟好久前写的代码了。

T1 数字游戏

P5660 数字游戏

大意:给定长度为 8 的 01 串,求 1 的个数

sb 题,考察字符串基本使用,当时好像 2:30 还没到就已经切完了

考场代码:

#include <iostream>
#include <cstdio>
#include <string>
//#define LOCAL

using namespace std;

int main()
{
#ifndef LOCAL
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
#endif
    string s;
    cin>>s;
    int ans=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='1') ans++;
    }
    printf("%d\n",ans);
    return 0;
}

T2 公交换乘

P5661 公交换乘

大意:坐一次地铁可以获取一张有效期 45 分钟的优惠券,可以凭券免费坐票价不超过地铁票价的公交车,优惠票可累积,使用时优先使用最先获得的

模拟即可,这里使用 vector 模拟优惠票的队列,代码并不优美但是能过。

坑点就在于

  • 使用票要使用最先获得的
  • 优惠票用过要删掉

记得当时在考场上发现队列不能用之后还自己研究 vector::erase 的用法

#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
//#define LOCAL
struct ticket{
    int price;
    ll time;
};
vector<ticket> q;

int main()
{
#ifndef LOCAL
    freopen("transfer.in","r",stdin);
    freopen("transfer.out","w",stdout);
#endif
    int n;
    scanf("%d",&n);
    ll ans=0;
    while(n--)
    {
        int type,price;
        ll t;
        scanf("%d %d %lld",&type,&price,&t);
        if(type==0)//如果坐地铁
        {
            ans+=price;//更新答案
            ticket tt={price,t};
            q.push_back(tt);//插入候选队
        }
        else if(type==1)//如果是公交
        {
            while(!(q.empty())&&t-q.front().time>45) q.erase(q.begin());//先删掉超时的优惠票
            bool flag=0;
            for(int i=0;i<q.size();i++)//查询符合标准的第一张优惠票
            {

                if(q[i].price>=price)
                {
                    q.erase(q.begin()+i);//直接删掉
                    flag=1;
                    break;
                }
            }
            if(!flag) ans+=price;//如果不存在就需要付原价
        }
    }
    printf("%lld\n",ans);
    return 0;
}

T3 纪念品

P5662 纪念品

谁叫我太菜,当时考场上骗了 10 分走人,现在看题解才写出正解。

大意:T 天,N 种纪念品,每天不同的纪念品都有不同的价格,小伟一开始有 M 金币,每天可以卖掉手中的纪念品换取金币,买进纪念品花费金币或者什么都不做。在第 T 天一定会卖出手中所有纪念品,求最高收益

分析题意,可以发现需要使用 dp,发现状态貌似很复杂,又可以买进又可以卖出,然而,注意到买进和卖出都可以进行无数次,因此我们可以把所谓一直持有的纪念品看成先将其卖出,又将其买进,效果是一样的,实质上就是每一天都做一次完全背包。

f_{i,j,k} 表示第 i 天,考虑前 j 种物品,手里有 k 金币时,在下一天全部卖出能达到的最大收益,则有方程

f_{i,j,k}=\max(f_{i,j,k},f_{i,j-1,k+p_i,j}+p_{i,j}-p_{i+1,j})

表示如果要了第 j 个物品,那么净收益即为 p_{i,j}-p_{i+1,j},从 f_{i,j-1,k+p_i,j} 转移而来,利用完全背包思想压一下维度然后改循环顺序即可以达到正确结果。

(第一维的天数是可以不要的,第二维的物品也是可以用滚动数组优化掉的,保留第三维即可)

#include <cstdio>
#include <cctype>
#include <cstring>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

int n,t,p[105][105],f[10005];

int main()
{
    t=read(),n=read();
    int m=read();
    for(int i=1;i<=t;i++)
        for(int j=1;j<=n;j++)
            p[i][j]=read();
    int ans=m;
    for(int i=1;i<t;i++)
    {
        memset(f,~0x3f,sizeof(f));//先赋负无穷
        f[ans]=ans;//初始值,什么都不干的情况
        for(int j=1;j<=n;j++)//枚举物品,从小到大即为完全背包
            for(int k=ans;k>=p[i][j];k--)//枚举金钱
                f[k-p[i][j]]=max(f[k-p[i][j]],f[k]+p[i+1][j]-p[i][j]);
        int maxn=0;//统计最优答案用
        for(int j=0;j<=ans;j++)
            maxn=max(maxn,f[j]);
        ans=maxn;
    }
    printf("%d\n",ans);
    return 0;
}

T4 加工零件

P5663 加工零件

大意:一个工厂正在生产零件,工人从 1 到 n 标号,某些工人之间有双向传送带。

如果 x 号工人想生产一个被加工到第 L (L \gt 1) 阶段的零件,则所有与 x 号工人有传送带直接相连的工人,都需要生产一个被加工到第 L – 1 阶段的零件(但 x 号工人自己无需生产第 L – 1 阶段的零件)。

如果 x 号工人想生产一个被加工到第 1 阶段的零件,则所有与 x 号工人有传送带直接相连的工人,都需要为 x 号工人提供一个原材料。

给定一些工单,即需要某工人生产某阶段的零件,求 1 号是否需要提供原材料。


先将其抽象成图论问题,以工人为节点,传送带为边来建图。

考虑暴力,虽然一定超时,但还是能给我们一些启示,不难发现暴力就是在看 a 与 1 之间是否存在长度为 L 的路径,同时我们又注意到:如果 L 为奇数,且从 1 到 a 存在一条奇数路径,且最小奇数路径长小于等于 L,那么 1 就必须提供原材料(为什么可以:你可以两个传送带之间来回跳,比如 1->2->1->2->1…,但如果最小的奇数路径大于 L,说明从 aL 个阶段也轮不到 1,就不行)同样的,如果 L 为偶数,且从 1 到 a 存在一条偶数路径,且最小偶数路径长小于等于 L,那么 1 就必须提供原材料。

这就给我们了正解的方法:找到每个点距离 1 点的最小奇数路径与偶数路径即可,这一过程实现可以使用 bfs(因为我当时还没学过最短路),然后判定每一个工单的时候按照奇偶数去找最短奇偶路径是否小于等于工单给定阶段就可以判定 YesNo

当然,我写的考场代码有一个小 bug,就是没有判断 1 点不连通的情况,然而 ccf 的数据没有这种特殊情况,所以也就 A 了这道题

考场代码:

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
//#define LOCAL
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
vector<int> g[100020];//存图
bool vis0[100020],vis1[100020];//bfs用
int minans0[100020],minans1[100020];//存储奇偶最短路
struct node{
    int n,time;
};
queue<node> q;
void bfs()
{
    memset(minans0,inf,sizeof(minans0));
    memset(minans1,inf,sizeof(minans1));
    q.push((node){1,0});
    while(!q.empty())
    {
        int curn=q.front().n;//当前的点
        int nxtc=q.front().time+1;//下一个点会经过的路径长
        q.pop();
        for(int i=0;i<g[curn].size();i++)
        {
            int nxt=g[curn][i];
            if(nxtc%2==0)//如果下一个点是偶数到达
            {
                if(vis0[nxt]==0)//如果未访问
                {
                    vis0[nxt]=1;
                    q.push((node){nxt,nxtc});
                    minans0[nxt]=min(nxtc,minans0[nxt]);//就更新这里的结果
                    //cout<<"no."<<nxt<<" "<<nxtc<<endl;
                }
            }
            if(nxtc%2==1)//反之如果是奇数,也一样
            {
                if(vis1[nxt]==0)
                {
                    vis1[nxt]=1;
                    q.push((node){nxt,nxtc});
                    minans1[nxt]=min(nxtc,minans1[nxt]);
                    //cout<<"no."<<nxt<<" "<<nxtc<<endl;
                }
            }
        }
    }
    return;
}

void add_edge(int u,int v)
{
    g[u].push_back(v);//注意是无向图
    g[v].push_back(u);
    return;
}


int main()
{
#ifndef LOCAL
    freopen("work.in","r",stdin);
    freopen("work.out","w",stdout);
#endif
    int n,m,q;
    scanf("%d %d %d",&n,&m,&q);
    while(m--)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        add_edge(u,v);
    }
    bfs();//预处理
    while(q--)
    {
        int a,l;
        scanf("%d %d",&a,&l);
        bool flag=0;
        if(l%2==0&&vis0[a]==1&&minans0[a]<=l) flag=1;//如果是偶数阶段并且能到达
        if(l%2==1&&vis1[a]==1&&minans1[a]<=l) flag=1;
        if(flag) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

解题报告 P2782 友好城市

题目内容

一条河,两岸有 n 对友好城市,分别给出坐标,友好城市之间需要开通航线,然而航线不可以两两交叉,求最多能开行的航线条数。

解题思路

首先将每对友好城市按照北岸坐标从小到大排序,不难发现,设已开通的航线的南北坐标分别为 S_1N_1,则如果另一条从 N_2S_2 的航线发生冲突,则会有 N_1>N_2S_1。所以我们如果将所有北岸坐标排好序之后,要使所有的航线不冲突,就让要选出来的南岸的城市坐标满足单调上升,这样才会不交叉。

所以排好序之后找南岸坐标的最长上升子序列就可以了。由于题目里面 n\le2\times 10^5,所以 O(n^2) 的算法无法通过,需要使用 O(n\log n)

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>

using std::sort;
using std::lower_bound;

struct city
{
    int n,s;
    bool operator<(const city &b)//按照北岸排序
    {
        return n<b.n;
    }
}a[(int)2e5+5];


int f[(int)2e5+5];

//快读省略

int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
        a[i].n=read(),
        a[i].s=read();
    sort(a+1,a+n+1);//按照北岸排序
    memset(f,0x7f,sizeof(f));
    int len=1;
    f[1]=a[1].s;
    for(int i=2;i<=n;i++)//找 LIS
    {
        if(a[i].s>=f[len])
            f[++len]=a[i].s;
        else
        {
            int p=lower_bound(f+1,f+len+1,a[i].s)-f;
            f[p]=a[i].s;
        }
    }
    printf("%d\n",len);
    return 0;
}

解题报告 CF607B Zuma

题目内容

CF607B

大意:给定一串序列,每次操作可以消除其中的一个回文串并将两侧拼一起,求消除所有元素所需的最小操作次数

解题思路

区间 dp

f_{i,j} 表示区间 [i,j] 需要的最小消除次数,接下来考虑转移:

显然,有

\begin{cases}
f_{i,i}=1\quad\
f_{i,i+1}=1\quad(a_i=a_j)\
f_{i,i+1}=2\quad(a_i\neq a_j)
\end{cases}

可发现的就是,如果串的长度为 1,则需要的消除次数为 1,如果长度为 2,则次数取决于这两个元素是否相等,相等就只需要一次,不相等就需要两次。

然后,一般地,如果当前枚举的两端点元素相等,说明可以在消除中间的元素的同时顺便消掉两边元素,但如果不相等,就只能枚举断点寻找最优划分方案,即:

\begin{cases}
f_{i,j}=f_{i+1,j-1}\qquad\qquad\qquad(a_i=a_j)\
f_{i,j}=\min_{k=i}^{j-1}\lbrace f_{i,k}+f_{k+1,j}\rbrace~(a_i\neq a_j)
\end{cases}

需要注意的是,不一定两端点元素相等了f_{i+1,j-1} 就是最优解,仍然需要考虑取断点的情况,否则会 WA,hack 数据:

10
1 2 3 5 3 2 1 1 3 1

上面的就是一个典型的不可通过直接取 f_{i+1,j-1} 得到答案的例子,如果在最后一步的时候直接套用 f_{2,9},得到的答案是 3,但是正确的结果是 2,由 f_{1,7}+f_{8,10} 得来

剩下的就很简单了,只需记得一开始 f 数组初始化为 inf 即可。

#include <cstdio>
#include <cctype>
#include <cstring>

const int maxn=505;
int n,a[maxn],f[maxn][maxn];

//快读已省略

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    n=read();
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
        a[i]=read(),f[i][i]=1;
    for(int i=1;i<n;i++)
        f[i][i+1] = 1+(a[i]!=a[i+1]);//处理长度为2的情况
    for(int l=3;l<=n;l++)
        for(int i=1,j=i+l-1;j<=n;i++,j++)
        {
            if(a[i]==a[j])
                f[i][j]=f[i+1][j-1];
            for(int k=i;k<j;k++)
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
        }
    printf("%d\n",f[1][n]);
    return 0;
}

解题报告 P3574 [POI2014]FAR-FarmCraft

题目内容

P3574

大意:村庄是一棵树,住在 1 号的管理要给每个房子送电脑,通过每个房子之间的道路需要 1 分钟,每个村民需要不同的时间安装电脑,而当管理把电脑送到村民后,村民会立即开始安装,最后管理会回到自己家给自己装电脑,求从管理出发到最后一个人装好电脑花费的时间。

解题思路

可以考虑每一个子树需要安装的最短时间。设住在 i 处的村民需要 c_i 的时间安装电脑, f_i 表示以 i 为根的子树全部安装好需要的最短时间,g_i 表示开车遍历以 i 为根的子树需要的最短时间,则有如下的方程:

f_i=\max(c_i,f_j+g_i+1)\
g_i\leftarrow g_i+g_j+2

其中 ji 的子节点,且 g_i 是动态更新的,就是遍历 j 之前的所有子树需要花的总时间。意思就是,对于一个 i 为根的子树,显然,第一次到 i 点的时候就让这里的村民开始装电脑得到的肯定更优,用这个时间与后面遍历下面节点的时间相比,总花费的时间是两者中间取最大的。而 f_j+g_i+1 的意义为,遍历过 j 节点之前的所有子节点需要的时间和 g_i 加上 j 节点需要的最短时间 f_j,至于 +1 就是从 i 节点走到 j 节点的花费。

而至于为什么是 +1 而不是 +2,是因为 \forall i:f_i-g_i\ge1,即等待的时间必然大于等于 1,所以只需要考虑从 i 进入 j 的时间,即为 1,而返回来的 1 的时间是被 f_j 覆盖掉的

不难发现,遍历的顺序会影响最终的结果,所以考虑贪心:可以发现,f_i-g_i 这段时间就是拿来等待的,做过接水问题的都知道要先处理等待时间大的,于是在转移前将子节点按照 f_i-g_i 排序即可。

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn=500010;
int n,c[maxn],f[maxn],g[maxn],tmp[maxn];
vector<int> G[maxn];

inline void ins(int a,int b)
{
    G[a].push_back(b);
    G[b].push_back(a);
    return;
}

inline bool cmp(int x,int y)
{
    return f[x]-g[x] > f[y]-g[y];
}

inline int read()
{
    char c = getchar();
    int s = 0, x = 0;
    while (!isdigit(c))
    {
        if(c == '-')
            x = 1;
        c = getchar();
    }
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

void dfs(int now,int fa)
{
    if(now!=1)//管理员的电脑最后装
        f[now]=c[now];
    int cnt=0;
    for(auto i:G[now])
        if(i!=fa)
            dfs(i,now);
    //一定要先遍历后记录儿子节点,不然会被下面的节点覆盖掉
    for(auto i:G[now])
        if(i!=fa)
            tmp[++cnt]=i;
    sort(tmp+1,tmp+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
        f[now]=max(f[now],f[tmp[i]]+g[now]+1),
        g[now]+=g[tmp[i]]+2;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        c[i]=read();
    int a,b;
    for(int i=1;i<n;i++)
    {
        a=read(),b=read();
        ins(a,b);
    }
    dfs(1,0);
    printf("%d\n",max(c[1]+g[1],f[1]));//在最后也要注意
    return 0;
}

解题报告 P6082 [JSOI2015]salesman

题目内容

P6082

大意:给定一棵 n 个点的树,有点权,从 1 号点开始一次旅行,最后回到 1 号点。每到达一个点,就能获得等于该点点权的收益。每个点都有进入该点的次数限制,且每个点的收益只获得一次。求最大收益以及方案是否唯一。

解题思路

不难发现,这道题满足最优子结构,一棵子树的答案可由这棵子树的子树合并而来。

注意到进入限制这个性质,到达这个点进入了一次,去到每一棵子树再回来又是进入这个点一次,所以实际上我们只能访问这个点的 限制次数减一 棵子树。

而为了保证最优,需要使用贪心思想,当将一个节点的所有子树的信息处理完之后,将其从大到小排序,取前面的限制次数减一个并加起来(当然如果加到负数就肯定不加了)。

至于解的唯一性,注意到如果一个子树下的某个子树的解不唯一,那么这个子树的解肯定也不唯一。以及如果对于他的一棵子树,这个子树的答案为 0,则走与不走这个子树的效果是相同的,答案就会不唯一。还有,如果最后一个选的子树 a 的答案与下一个待选子树 b 的答案相同,说明可以选 a 也可以选 b,效果都是一样的,也会产生多解。

代码如下:

#include <utility>
#include <cstdio>
#include <cctype>
#include <queue>

using std::priority_queue;
using std::make_pair;
using std::vector;
using std::pair;

const int maxn=1e5+5;
int n,money[maxn],stop[maxn];
int f[maxn][2];

vector<int> g[maxn];

inline void ins(int from,int to)
{
    g[from].push_back(to);
    g[to].push_back(from);
    return;
}

inline int read()
{
    char c = getchar();
    int s = 0, x = 0;
    while (!isdigit(c))
    {
        if(c == '-')
            x = 1;
        c = getchar();
    }
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

void dfs(int now,int fa)
{
    if(g[now].size()==1)//这是判断是否为叶子节点的
    {
        f[now][0]=money[now];
        return;
    }
    priority_queue<pair<int,int> > q;//排序用
    for(int i=0;i<g[now].size();i++)//访问下面的节点
    {
        if(g[now][i]!=fa)
        {
            dfs(g[now][i],now);//继续递归
            q.push(make_pair(f[g[now][i]][0],g[now][i]));//并且加入队列
        }
    }
    int lastChosen;
    for(int i=1; (!q.empty()) && (now==1 ? 1 : i<stop[now]);i++)
    {
        int to=q.top().second,val=q.top().first;
        if(val<0)//如果现在这棵子树已经小于 0 了,说明会产生负贡献,直接舍弃
            break;
        if(val==0)//有多解
            f[now][1]=1;
        f[now][0] += val;
        lastChosen=val;
        f[now][1] |= f[to][1];//下面的答案有多解的话也会产生多解
        q.pop();
    }
    f[now][0]+=money[now];
    if(q.size() && q.top().first==lastChosen)//如果下一个备选答案与上一个的相同,则有多解
        f[now][1]=1;
    return;
}

int main()
{
    n=read();
    for(int i=1;i<n;i++)
        money[i+1]=read();
    for(int i=1;i<n;i++)
        stop[i+1]=read();
    int from,to;
    for(int i=1;i<n;i++)
    {
        from=read(),to=read();
        ins(from,to);
    }
    dfs(1,0);
    printf("%d\n",f[1][0]);
    if(f[1][1])
        printf("solution is not unique\n");
    else
        printf("solution is unique\n");
    return 0;
}

解题报告 P4170 [CQOI2007]涂色

题目内容

P4170

大意:给出一块木板,要求涂色,后覆盖前,求最小笔刷数

解题思路

区间 dp。

不难发现,定义状态 f_{i,j}[i,j] 的最少次数可以满足最优子结构和无后效性,具体就是要看如何转移。

枚举端点 ij,发现如果有 s_i=s_j 的话,相当于第一次涂色的时候多涂一格,转移方程为 f_{i,j}=\min(f_{i,j-1},f_{i+1,j})

但如果 s_i\neq s_j 的话,说明没办法直接多涂一格,需要枚举中间的断点 k,由于枚举 k 的过程中必然能找到一种划分方式使得总的涂色次数加起来最优,因此只需要将断点左右加起来取最小值就可以得到该区间的答案,故有如下方程:

f_{i,j}=\min_{k\in[i,j)} \lbrace f_{i,k}+f_{k+1,j}\rbrace

#include <cstdio>
#include <cstring>

int f[55][55];

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    int n;
    char s[55];
    scanf("%s",s+1);
    n=strlen(s+1);
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
        f[i][i]=1;
    for(int l=1;l<n;l++)
        for(int i=1,j=l+1;j<=n;i++,j++)
            if(s[i]==s[j])
                f[i][j]=min(f[i][j-1],f[i+1][j]);
            else
                for(int k=i;k<j;k++)
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
    printf("%d\n",f[1][n]);
    return 0;
}

解题报告 P4933 大师

题目内容

P4933

大意:求等差子序列总个数(包括长度为 1 或 2 的)

解题思路

dp,先考虑状态的设计和转移。

不难发现,如果我们考虑第 i 个数,如果第 i 个数可以接上前面的某一个等差数列,那么答案就会增加前面等差数列的长度再加一,所以考虑将以 i 结尾的等差数列存进状态里面。

我们可以令 f_i 表示以 i 结尾的等差数列的长度,但是发现貌似不同的公差会造成不同的后效性,所以我们需要将公差也存储下来,即 f_{i,j} 表示以 i 结尾,公差为 j 的最长等差数列的长度,由于公差可能为负,故处理时要加上 20000 防止下标出锅

转移:

f_{i,k}\leftarrow f_{i,k}+f_{j,k}+1

同时 ans+=f[j][k]+1

注意取模就可以了

#include <cstdio>
#include <cctype>
using namespace std;

const int maxn=1005,mod=998244353;
int n,h[maxn];
int ans,f[maxn][20005<<1];

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        h[i]=read();
    for(int i=1;i<=n;i++)
    {
        ans++;
        for(int j=1;j<i;j++)
        {
            int cur=h[i]-h[j]+20000;
            f[i][cur]+=f[j][cur]+1;
            f[i][cur]%=mod;
            ans+=f[j][cur]+1;
            ans%=mod;
        }
    }
    printf("%d\n",ans%mod);
    return 0;
}

解题报告 P2831 愤怒的小鸟

题目内容

P2831

大意:(0,0) 处有一弹弓,有 n 只猪猪,弹弓发出的炮弹路径为 y=ax^2+bx,其中 a > 0,求最少的抛物线数量打掉所有猪猪。

解题思路

一开始的暴搜调了我很久,但是最后都只有 60 分,具体的思路就是两只两只的枚举猪猪,如果发现两只可以构成合法抛物线,那么就清算抛物线上的其他猪猪然后继续暴搜,但是复杂度比较高。状态的存储使用状压。

#include <cstdio>
#include <cmath>
#include <bitset>
#include <cstring>
#include <iostream>
#define EPS 1e-6
using namespace std;

class P2831
{
private:

    struct point
    {
        double x,y;
    };

    int ans;
    int n,m;
    point pig[19];
    int vis[1<<18];


    inline bool ison(point p,double a,double b)//判断点在不在抛物线上
    {
        return fabs(a*p.x*p.x+b*p.x-p.y)<=EPS;
    }

    inline bool calc(point d1,point d2,double &a,double &b)//计算过(x1,y1)和(x2,y2)的抛物线表达式
    {
        if(fabs(d1.x-d2.x)<EPS)
        {
            //cout<<"debug1"<<endl;
            return false;
        }
        if(fabs(d2.y/d2.x-d1.y/d1.x)<EPS)
        {
            //cout<<"debug2"<<endl;
            return false;
        }
        b=(d1.y*d2.x*d2.x/d1.x/d1.x-d2.y)/((d2.x*d2.x/d1.x)-d2.x);
        a=(d1.y-b*d1.x)/d1.x/d1.x;
        //cout<<"a:"<<a<<" b:"<<b<<endl;
        if(a>0)
            return false;
        return true;
    }

    void dfs(int cur,int opt,int step)
    {
        vis[cur]=min(vis[cur],step);
        //cout<<"step:"<<step<<' '<<cur<<endl;
        if(cur==(1<<n)-1)
        {
            ans=min(ans,step);
            return;
        }
        if(opt==1 && step>n/3.0+1)
            return;
        if(step>=ans || step>vis[cur])
            return;
        for(int i=0;i<n;i++)
        {
            bool flag=0;
            int now=cur;
            if(now&(1<<i))
                continue;
            now|=(1<<i);
            for(int j=0;j<n;j++)
            {
                int now2=now;
                if(now2&(1<<j))
                    continue;
                double a,b;
                if(!calc(pig[i],pig[j],a,b))
                    continue;
                flag=1;
                now2|=(1<<j);
                for(int k=0;k<n;k++)
                    if((!now2&(1<<k)) && ison(pig[k],a,b))
                        now2|=(1<<k);
                dfs(now2,opt,step+1);
            }
            if(!flag)
                dfs(now,opt,step+1);
        }
    }

public:

    int solve()
    {
        ans=0x3f3f3f3f;
        memset(vis,0x3f,sizeof(vis));
        scanf("%d %d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%lf %lf",&pig[i].x,&pig[i].y);
        dfs(0,m,0);
        return ans;
    }
};

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        P2831 a;
        printf("%d\n",a.solve());
    }
    return 0;
}

于是我放弃了调暴搜,在题解区发现了一种神奇的东西叫状压 dp,用 f_i 表示状态 i 需要的最少抛物线条数。同时抛物线预处理成能通过的点的集合,记作 para_j,转移方程如下:

f_{i|para_j}=\min(f_{i|para_j},f_i+1)

预处理抛物线的时候首先枚举单个的猪猪,因为每只猪猪必过一个抛物线,然后再枚举第二个猪猪,如果能构成的抛物线合法的话再将其他在抛物线上的点加入即可。

关于数学:要求过 (x_1,y_1)(x_2,y_2) 的抛物线 y=ax^2+bxab 的值,列出来式子然后消元即可。

b=\frac{\frac{y_1x^2_2}{x_1^2}-y_2}{\frac{x_2^2}{x_1}-x_2}\
a=\frac{y_1-bx_1}{x_1^2}

代码如下:

#include <cstdio>
#include <cmath>
#include <cstring>
#define EPS 1e-6
using namespace std;

struct point
{
    double x,y;
};

int n,m,para[200],f[1<<18],cnt;

inline bool ison(point p,double a,double b)//判断点在不在抛物线上
{
    return fabs(a*p.x*p.x+b*p.x-p.y)<=EPS;
}

inline bool calc(point d1,point d2,double &a,double &b)//计算过(x1,y1)和(x2,y2)的抛物线表达式
{
    if(fabs(d1.x-d2.x)<EPS)//判断横坐标相等的情况
        return false;
    if(fabs(d2.y/d2.x-d1.y/d1.x)<EPS)//判断构不成抛物线的情况
        return false;
    b=(d1.y*d2.x*d2.x/d1.x/d1.x-d2.y)/((d2.x*d2.x/d1.x)-d2.x);
    a=(d1.y-b*d1.x)/d1.x/d1.x;
    if(a>0)
        return false;
    return true;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

void pre()//预处理
{
    scanf("%d %d",&n,&m);
    memset(f,0x3f,sizeof(f));//先赋极大值
    cnt=0;//cnt为抛物线的数量
    point pig[18];
    for(int i=0;i<n;i++)
        scanf("%lf %lf",&pig[i].x,&pig[i].y);
    for(int i=0;i<n;i++)
    {
        para[cnt++]=1<<i;//先加入一个新抛物线
        for(int j=i+1,vis=0;j<n;j++)//定义的vis是枚举过的小猪,避免重复
        {
            if((1<<j)&vis)//判重
                continue;
            double a,b;
            if(!calc(pig[i],pig[j],a,b))//如果不合法
                continue;
            para[cnt]=1<<i;//先暂时加进去只有第一只猪猪的抛物线
            for(int k=j;k<n;k++)//然后枚举加新点进去
            {
                if(ison(pig[k],a,b))//如果第k只猪猪在上面
                {
                    vis|=(1<<k);//更新vis数组
                    para[cnt]|=(1<<k);//更新抛物线
                }
            }
            cnt++;//然后抛物线的条数要加一
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        pre();
        f[0]=0;
        for(int i=0;i<(1<<n);i++)//枚举每个状态
            for(int j=0;j<cnt;j++)//枚举每一条抛物线
                f[i|para[j]]=min(f[i|para[j]],f[i]+1);//状态转移
        printf("%d\n",f[(1<<n)-1]);//输出答案
    }
    return 0;
}

解题报告 P1336 最佳课题选择

题目内容

P1336

一共写 n 篇论文,一共 m 个课题,对于第 i 个课题如果写 x 篇则需花费 A_i\times x^{B_i} 的时间,求最小时间

解题思路

泛化物品的背包,价值随着分给他的大小而变化。由于数据范围比较小,所以直接枚举第 i 个课题选择的数量 k 即可,转移方程:

f_{i,j}=\min(f_{i,j},f_{i-1,j-k}+A_i\times k^{B_i})

然后边界就是 f_{1,i}=A_1\times i^{B_1},最后使用滚动数组优化一下即可

不开 long long 见祖宗

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
typedef long long ll;

ll n,m,a[25],b[25],f[205];

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline ll min(ll a,ll b)
{
    return a<b?a:b;
}

inline ll ksm(ll base,ll p)//写了个快速幂
{
    ll ans=1;
    for(;p;p>>=1)
    {
        if(p&1)
            ans*=base;
        base*=base;
    }
    return ans;
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
        a[i]=read(),b[i]=read();
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++)
        f[i]=a[1]*ksm(i,b[1]);
    //边界
    for(int i=2;i<=m;i++)
        for(int j=n;j>=0;j--)
            for(int k=0;k<=j;k++)
                f[j]=min(f[j],f[j-k]+a[i]*ksm(k,b[i]));//进行转移
    printf("%lld\n",f[n]);
    return 0;
}