分治，维护一个dp数组，当递归到区间[l,r]时，需要保证这个dp数组维护的是除去[l,r]以外的dp数组
维护其实很简单，就是递归左区间是先将右区间加入，然后再将左区间加入（要先复原）然后递归右区间即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 2005 4 #define oo 0x3f3f3f3f 5 #define mid (l+r>>1) 6 int n,m,a[N*10],c[N*10],f[N],ff[N],g[21][N]; 7 void add(int l,int r){ 8 for(int i=l;i<=r;i++){ 9 memcpy(ff,f,sizeof(f)); 10 for(int j=0;j<m;j++) 11 f[j]=min(f[j],ff[(j+m-a[i])%m]+c[i]); 12 } 13 } 14 void dfs(int l,int r,int s){ 15 if (l==r){ 16 long long ans=0; 17 for(int i=0;i<m;i++) 18 if (f[i]==oo)ans--; 19 else ans+=f[i]; 20 printf("%lld\n",ans); 21 return; 22 } 23 memcpy(g[s],f,sizeof(f)); 24 add(mid+1,r); 25 dfs(l,mid,s+1); 26 memcpy(f,g[s],sizeof(f)); 27 add(l,mid); 28 dfs(mid+1,r,s+1); 29 } 30 int main(){ 31 scanf("%d%d",&n,&m); 32 for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&c[i]); 33 memset(f,oo,sizeof(f)); 34 f[0]=0; 35 dfs(1,n,0); 36 }