线性DP习题题解总结

• 背包扩展
• 状态的设置
• 状态转移的优化
• 区间dp

A [ARC066-C]Tak and Cards

题目描述 高桥有$n$个整数。第$i$个数的值为$x_i$。

高桥从这些整数中挑选1个以上，想把选择的整数的平均数等于$A$的数。

问有多少种方案。

输入格式 第一行读入N,A；

接下来一行读入N个数

输出格式 一个数，表示要求的方案。

样例数据
input
4 8
7 9 8 9
output
5

求方案数的dp该如何设置状态？动态规划首先想到的应该是“求什么设什么”，不妨设$f[i][j][k]$表示前i个数选取j个，累加和为k的方案数。那么首先$f[i][j][k]$中必然包含$f[i-1][j][k]$，即第i个数不选。可以不选，自然也可以选。我们可以得知$f[i][j][k]$必然还包含$f[i-1][j-1][k-a[i]]$。这样就完成了吗？当然没有，思考，$k$和$a[i]$的大小关系并不确定。所以我们需要额外判断。
综上可得出状态转移方程：

     f[i][j][k]+=f[i-1][j][k];
     if(k>=a[i]&&j>=1) f[i][j][k]+=f[i-1][j-1][k-a[i]];

其他细节见代码。
具体代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,A,a[55],f[55][55][2510];
long long ans;
inline int read(){//快读
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int main(){
    n=read(); A=read();
    for(int i=1;i<=n;i++) a[i]=read();
    f[0][0][0]=1;//虽说不存在一个数都不选的情况，但可以根据它推算后面
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++)
            for(int k=0;k<=n*A;k++){//k最大不超过n*A,减少多余的枚举
            	f[i][j][k]+=f[i-1][j][k];//状态转移
            	if(k>=a[i]&&j>=1) f[i][j][k]+=f[i-1][j-1][k-a[i]];
			}
	for(int i=1;i<=n;i++) ans+=f[n][i][i*A];//平均数为A，不多解释
	cout<<ans;//问方案数需要多个方案的方案数累加和
    return 0;
}

本题本质上是0/1背包，可以优化掉第一维，此处不再详细解释，核心代码如下。

    for(int i=0;i<n;i++)
	    for(int j=n-1;j>=0;j--)//倒着枚举
	        for(int k=0;k<=n*A;k++)
	  	        f[j+1][k+a[i]]+=f[j][k];
    for(int i=1;i<=n;i++)    ans+=f[i][k*i];

B [JOISC2014] 挂饰

题目描述 JOI君有N个装在手机上的挂饰，编号为1…N。 JOI君可以将其中的一些装在手机上。

JOI君的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。每个挂饰要么直接挂在手机上，要么挂在其他挂饰的挂钩上。直接挂在手机上的挂件最多有1个。

此外，每个挂饰有一个安装时会获得的喜悦值，用一个整数来表示。如果JOI君很讨厌某个挂饰，那么这个挂饰的喜悦值就是一个负数。

JOI君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰，而且一个都不挂也是可以的。

输入格式 第一行一个整数N，代表挂饰的个数。

接下来N行，第i行($1<=i<=N$)有两个空格分隔的整数$A_i$和$B_i$，表示挂饰 $i$有$A_i$个挂钩，安装后会获得$B_i$的喜悦值。

输出格式 输出一行一个整数，表示手机上连接的挂饰总和的最大值

样例
input
5
0 4
2 -2
1 -1
0 1
0 3
output
5

总结下题目：
挂饰：挂钩，价值，且价值可以为负
挂饰必须挂在挂钩上，手机上可以直接挂一个挂饰。
根据经验，我们显然可以把挂饰分为四类：

（1）有挂钩，价值为正（这类必然对答案有正向贡献，必选）。
（2）无挂钩，价值为负（这类必然不选，即使还有剩余挂钩也不会选）。
（3）有挂钩，价值为负（虽然价值为负，但挂钩的存在让它没那么一无是处，挂钩可能带来更大的利益）。
（4）无挂钩，价值为正（在考虑范围内，可以作为一串的结尾）。

对于第2种物品，
可以用f[i]表示当还有i个剩余挂
钩时的最大装饰度，
做一次01背包即可求f[]数组。

对于第3种物品，
只要拿价值最大的就可以了，
那么降序排序后的前缀和s[i]就可以表示当挂钩
数为[i]时的最大装饰度。

那么答案就是max(f[i]+s[i])了，
注意还要加上第1
种物品给答案的贡献。

#include<bits/stdc++.h>
using namespace std;
const int Inf=-1e9;
struct decoration{
	int con,vl;//挂钩数，喜悦值 
}a[2010];
int n,f[3010][3010],ans=Inf;
bool mycmp(decoration x,decoration y){
	return x.con>y.con;
}
inline int read(){//快读
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)
    	a[i].con=read(),a[i].vl=read();
	sort(a+1,a+n+1,mycmp);
	for(int i=0;i<=n;i++) f[0][i]=Inf,f[i][n+1]=Inf;
    f[0][1]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=n;j++)
            f[i][j]=max(f[i-1][j],f[i-1][max(j-a[i].con,0)+1]+a[i].vl);
    for(int i=0;i<=n;i++) ans=max(ans,f[n][i]);
    printf("%d\n",ans);
    return 0;
}