题意：给一个数组，和q次询问，每次询问删除数组三个数（询问结束后补上），问能不能挑出十个数和为87
首先这题的坑是数据存在N小但是Q大的情况，打表比直接求快= = 卡直接求的做法....（duliu
定义dp[i][j][k]：前i个数，选了j个，和为k是否有这个状态。
dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-a[i]]
复杂度O(N^4*T*10*87)=O(1e10) ，显然超时的代码
#include<bits/stdc++.h> using namespace std; #define LL long long const LL mod = 1000000007; const int MX = 1e3+1; int a[100],n;vector <int> v; int dp[15][55][88]; bool ju[55][55][55]; void judge(int x,int y,int z){ v.clear(); v.push_back(0); for(int i=1;i<=n;i++){ if(i==x||i==y||i==z||a[i]>87)continue; v.push_back(a[i]); } for(int i=0;i<=10;i++)for(int j=0;j<=n;j++)for(int k=0;k<=87;k++)dp[i][j][k]=0; dp[0][0][0]=1; for(int w=1;w<v.size();w++){ for(int j=0;j<=87;j++) dp[0][w][j]=dp[0][w-1][j]; for(int i=1;i<=10;i++){ for(int j=0;j<=87;j++){ dp[i][w][j]=dp[i][w-1][j]; if(j-v[w]>=0) dp[i][w][j]|=dp[i-1][w-1][j-v[w]]; } } } if(dp[10][v.size()-1][87])ju[x][y][z]=1; } int main(){ int T;scanf("%d",&T);while(T--){ scanf("%d",&n);for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } memset(ju,0,sizeof(ju)); for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ for(int k=j;k<=n;k++){ judge(i,j,k); } } } int q;scanf("%d",&q);while(q--){ int sc[4];scanf("%d%d%d",&sc[0],&sc[1],&sc[2]); sort(sc,sc+3); if(ju[sc[0]][sc[1]][sc[2]])printf("Yes\n"); else printf("No\n"); } } return 0; }bitset优化，复杂度O(N^4*T*10*87/64)=O(4e8)，勉强可以卡过，注意记录上一次更新的结果
#include<bits/stdc++.h> using namespace std; #define LL long long const LL mod = 1000000007; const int MX = 1e3+1; int a[100],n;vector <int> v; bitset<88>dp[15][55]; bool ju[55][55][55]; void judge(int x,int y,int z){ v.clear(); v.push_back(0); for(int i=1;i<=n;i++){ if(i==x||i==y||i==z||a[i]>87)continue; v.push_back(a[i]); } for(int i=0;i<=10;i++)for(int j=0;j<=n;j++)dp[i][j].reset(); dp[0][0][0]=1; for(int w=1;w<v.size();w++){ dp[0][w]|=dp[0][w-1]; for(int i=1;i<=10;i++){ dp[i][w]|=dp[i][w-1]; dp[i][w]|=dp[i-1][w-1]<<v[w]; } } if(dp[10][v.size()-1][87])ju[x][y][z]=1; } int main(){ int T;scanf("%d",&T);while(T--){ scanf("%d",&n);for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } memset(ju,0,sizeof(ju)); for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ for(int k=j;k<=n;k++){ judge(i,j,k); } } } int q;scanf("%d",&q);while(q--){ int sc[4];scanf("%d%d%d",&sc[0],&sc[1],&sc[2]); sort(sc,sc+3); if(ju[sc[0]][sc[1]][sc[2]])printf("Yes\n"); else printf("No\n"); } } return 0; }然后类似01背包，可以用滚动数组再优化一下，注意前一次更新对后一次更新的影响（后效性
#include<bits/stdc++.h> using namespace std; #define LL long long const LL mod = 1000000007; const int MX = 1e3+1; int a[100],n; bitset<88>dp[15]; bool ju[55][55][55]; void judge(int x,int y,int z){ for(int i=0;i<=10;i++)dp[i].reset(); dp[0][0]=1; for(int w=1;w<=n;w++){ if(w==x||w==y||w==z)continue; for(int i=10;i>=1;i--){ dp[i]|=dp[i-1]<<a[w]; } } if(dp[10][87])ju[x][y][z]=1; } int main(){ int T;scanf("%d",&T);while(T--){ scanf("%d",&n);for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } memset(ju,0,sizeof(ju)); for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ for(int k=j;k<=n;k++){ judge(i,j,k); } } } int q;scanf("%d",&q);while(q--){ int sc[4];scanf("%d%d%d",&sc[0],&sc[1],&sc[2]); sort(sc,sc+3); if(ju[sc[0]][sc[1]][sc[2]])printf("Yes\n"); else printf("No\n"); } } return 0; }
