#include#include#define fo(i,a,b) for(i=a;i<=b;i++)#define fd(i,a,b) for(i=a;i>=b;i–)using namespace std;typedef long long ll;const int maxn=2000;ll f[maxn][maxn],g[maxn][maxn];ll a[maxn],b[maxn],c[maxn],d[maxn];ll i,j,k,l,t,n,m,ans,x,y,x1,y1,x2,y2,dx,dy;void dp(){ int i,j,k; for(i=0;i<=n;i++) for(j=0;j<=800;j++) f[i][j]=1000000000000; f[0][0]=0; for(i=0;i<=n-1;i++) for(j=0;j<=800;j++) if (f[i][j]!=1000000000){ if (f[i][j]+d[i+1]<f[i+1][j+a[i+1]]){ f[i+1][j+a[i+1]]=f[i][j]+d[i+1]; g[i+1][j+a[i+1]]=1; } if (f[i][j]<f[i+1][j]){ f[i+1][j]=f[i][j]; g[i+1][j]=0; } } k=-1; for(i=m;i<=800;i++) if (f[n][i]!=1000000000&&(k==-1||f[n][i]<f[n][k])) k=i; x=y=0; for(i=n;i>=l;i–){ if (g[i][k]){ k-=a[i]; x+=b[i]; y+=c[i]; } }}void solve(ll x1,ll y1,ll x2,ll y2){ dx=abs(x1-x2); dy=abs(y1-y2); ll i; for(i=l;i<=n;i++) d[i]=b[i]dy+c[i]dx; dp(); ll xx=x,yy=y; if ((xxx1&&yyy1)||(xxx2&&yyy2)) return; else{ ans=min(ans,xxyy); solve(x1,y1,xx,yy); solve(xx,yy,x2,y2); }}int main(){ scanf("%lld%lld",&n,&m); fo(i,1,n) scanf("%lld%lld%lld",&a[i],&b[i],&c[i]); for(i=l;i<=n;i++) d[i]=b[i]; dp(); x1=x;y1=y; for(i=l;i<=n;i++) d[i]=c[i]; dp(); x2=x;y2=y; ans=min(x1y1,x2*y2); solve(x1,y1,x2,y2); printf("%lld\n",ans);}
有懂的铁铁吗?可以帮忙看看,大概加一下注释吗,真的看不懂了,感谢。