pq

题目描述

小q 的女朋友送给小q nn个整数。但是这些数太大了，小q 的女朋友拿不动，于是拜托小q把这些数减少一些。

小q 每次可以选择其中的两个x,yx,y (不能同时选择同一个数) 变成x−P,y−Qx−P,y−Q，现在他希望能知道最多能帮女朋友减掉多少P,QP,Q。

输入

第一行一个数表示nn。

第二行由空格隔开的nn个数。

第三行两个数，表示p,qp,q。

输出

一行一个数，表示能减掉的PP和QQ的总和。

样例输入

<span style="color:#333333"><span style="color:#333333">输入样例1
2
100 100
50 50
输入样例2
3
50 250 50
50 100
输入样例3
4
123 456 789 555
58 158</span></span>

样例输出

<span style="color:#333333"><span style="color:#333333">输出样例1
200
输出样例2
300
输出样例3
1728</span></span>

提示

对于前20%的数据，n≤5;

对于100%100%的数据，1≤n≤50,ci≤2000,50≤P,Q≤2000。

来源

2018年10月hnsdfz集训

solution

令状态f[i][x][y] 表示前i个数，p有x个没有匹配，q有y个没有匹配

我们枚举i被分成了几个p和几个q

设分了nx个p ny个q，

然后分类讨论

 if(nx<=y&&ny<=x)
f[x-ny][y-nx]=max(f[x-ny][y-nx],g[x][y]+nx+ny);

意思是nx ny全部用于匹配原来未匹配的x，y

if(nx<=y&&ny>x)
f[0][y+ny-x-nx]=max(f[0][y+ny-x-nx],g[x][y]+nx+x);

意思是多出的x都被匹配完了 ny剩的加到多出的y上

if(nx>y&&ny<=x)
f[nx+x-y-ny][0]=max(f[nx+x-y-ny][0],g[x][y]+ny+y);

同2

if(nx>y&&ny>x)
f[nx-y][ny-x]=max(f[nx-y][ny-x],g[x][y]+x+y);

意思是ny nx都有剩（恰好交换了）

还有几个问题

1. 50*2000*2000 MLE

滚动数组

2.TLE

（1）不需要枚举p和q，只要枚举p，贪心取q（一定最优）

（2）真正有用的的dp范围只有[40][40] [0][2000] [2000][0]

因为，加入一个数时

啊我忘了（留坑待填）

orz神犇拒绝滚动怒卡空间

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int n,pp,qq,s[55],f[2005][2005],flag[2005][2005];
int g[2004][2005];
struct node{
    int id,x,y;
}t,ne;
queue<node>q;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&s[i]);
    cin>>pp>>qq;
    t.id=t.x=t.y=0;q.push(t);int nn=0;
    while(!q.empty()){
        node a=q.front();q.pop();
        ///cout<<a.id<<' '<<a.x<<' '<<a.y<<' '<<f[a.id][a.x][a.y]<<endl;
        if(a.id==n)break;
        if(a.id>nn){
            for(int j=0;j<=2000;j++){
                g[0][j]=f[0][j];g[j][0]=f[j][0];
                f[0][j]=0;f[j][0]=0;
                flag[0][j]=0;flag[j][0]=0;
            }
            for(int i=1;i<=40;i++)
            for(int j=1;j<=40;j++){
                g[i][j]=f[i][j];f[i][j]=0;flag[i][j]=0;
            }
             
            nn=a.id;
        }
        int i=a.id,x=a.x,y=a.y;
         
        for(int nx=0;nx*pp<=s[i+1];nx++){
            int la=s[i+1]-nx*pp;
            int ny=la/qq;
            if(nx<=y&&ny<=x)
            {
                f[x-ny][y-nx]=max(f[x-ny][y-nx],g[x][y]+nx+ny);
                if(!flag[x-ny][y-nx]){
                    flag[x-ny][y-nx]=1;
                    ne.id=i+1;ne.x=x-ny;ne.y=y-nx;
                    q.push(ne);
                }
            }
            if(nx<=y&&ny>x){
                f[0][y+ny-x-nx]=max(f[0][y+ny-x-nx],g[x][y]+nx+x);
                if(!flag[0][y+ny-x-nx]){
                    flag[0][y+ny-x-nx]=1;
                    ne.id=i+1;ne.x=0;ne.y=y+ny-x-nx;
                    q.push(ne);
                }
            }
            if(nx>y&&ny<=x){
                f[nx+x-y-ny][0]=max(f[nx+x-y-ny][0],g[x][y]+ny+y);
                if(!flag[nx+x-y-ny][0]){
                    flag[nx+x-y-ny][0]=1;
                    ne.id=i+1;ne.x=nx+x-y-ny;ne.y=0;
                    q.push(ne);
                }
            }
            if(nx>y&&ny>x){
                f[nx-y][ny-x]=max(f[nx-y][ny-x],g[x][y]+x+y);
                if(!flag[nx-y][ny-x]){
                    flag[nx-y][ny-x]=1;
                    ne.id=i+1;ne.x=nx-y;ne.y=ny-x;
                    q.push(ne);
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=2000;i++)
    for(int j=0;j<=2000;j++)ans=max(ans,f[i][j]*(pp+qq));
    cout<<ans<<endl;
    return 0;
}