JOI2012本選3番
時間がSにかぶるときだけ気をつけてdpすればOK。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int n,S,T; int A[3010],B[3010]; int dp[3010][3010]; int rec(int store,int time){ if(store==n) return 0; else if(dp[store][time]!=-1) return dp[store][time]; else{ int res=rec(store+1,time); if(time<S&&S<time+B[store]){ if(S+B[store]<=T){ res=max(res,rec(store+1,S+B[store])+A[store]); } }else{ if(time+B[store]<=T){ res=max(res,rec(store+1,time+B[store])+A[store]); } } return dp[store][time]=res; } } int main(){ scanf("%d%d%d",&n,&T,&S); for(int i=0;i<n;i++) scanf("%d%d",A+i,B+i); memset(dp,-1,sizeof(dp)); int ans=rec(0,0); printf("%d\n",ans); return 0; }