可达性dp。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1050 using namespace std; int n,b,l,c[maxn]; bool f[60][maxn]; int main() { scanf("%d%d%d",&n,&b,&l); for (int i=1;i<=n;i++) scanf("%d",&c[i]); f[0][b]=true; for (int i=1;i<=n;i++) for (int j=0;j<=l;j++) { f[i][j]=false; if (j>=c[i]) f[i][j]|=f[i-1][j-c[i]]; if (j+c[i]<=l) f[i][j]|=f[i-1][j+c[i]]; } for (int i=l;i>=0;i--) if (f[n][i]) {printf("%d ",i);return 0;} printf("-1 "); return 0; }