题目：https://www.luogu.org/problemnew/show/P4141
这道题教会我dp的新姿势。
从每一个体积来看比较方便。
发现对于一个特定的体积，它从1~n的变化轨迹就是不断地+=dp[ k-a[i] ]。（dp[ k-a[i] ]保证没有选 i （倒序！））
所以不选 i 对于这个体积来说竟然就是 - = dp[ k-a[i] ]！
于是可以先n^2求出到最后所有的体积对应的方案，然后去各个地方 - = dp[ k-a[i] ]。
需要注意的是直接减的话，dp[ k-a[i] ]里是包含了“选 i ”这种情况的。
正好自己正在求“不选 i ”的种种体积，所以就再开一个数组，正序遍历，用刚才求出的值就好了。
我还在想什么正着dp再倒着dp之类，结果还是n^3；
看看别人，发现简单地n^3竟然就是枚举 i 不选，然后正常n^2，从1~n遍历到 i 的时候直接跳过……
这道题之所以可以随便加加减减、跳过什么的，可能因为仔细分析一下，它只涉及加减，与乘什么的没有关系，所以交换律使得可以任意时刻直接减掉不需要的。
但是从每一个体积来分析，得出思路是很重要的角度。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=2005; int n,m,a[N],dp[N],tp[N]; int rdn() { int ret=0;char ch=getchar(); while(ch>‘9‘||ch<‘0‘)ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘)(ret*=10)+=ch-‘0‘,ch=getchar(); return ret; } int main() { n=rdn();m=rdn(); for(int i=1;i<=n;i++)a[i]=rdn(); dp[0]=1; for(int i=1;i<=n;i++) for(int j=m;j>=a[i];j--)//倒序 (dp[j]+=dp[j-a[i]])%=10; for(int i=1;i<=n;i++) { memcpy(tp,dp,sizeof dp); for(int j=1;j<=m;j++) { tp[j]=(dp[j]-(j>=a[i]?tp[j-a[i]]:0)+10)%10;//不然dp[j-a[i]]里包含选了一个a[i]的情况 printf("%d",tp[j]%10); } printf("\n"); } return 0; }
原文：https://www.cnblogs.com/Narh/p/9189491.html