dp

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 const int maxn=10010;  6 int dp[11][10010];  7 int belong[10010];  8 int w[10010],v[10010];  9 int flag[20]; 10 int main() 11 {
    12     int n,m,k,i,j,x; 13     while(scanf("%d%d%d",&n,&m,&k)!=EOF) 14     {
    15         memset(flag,0,sizeof(flag)); 16         for(i=1;i<=n;i++) 17         {
    18             scanf("%d%d%d",&belong[i],&w[i],&v[i]); 19             flag[belong[i]]=1; 20         } 21         int vis=0; 22         for(i=1;i<=k;i++) 23             if(!flag[i]) 24             {
    25                 vis=1; 26                 printf("Impossible\n"); 27                 break; 28             } 29         if(vis) continue; 30         memset(dp,0,sizeof(dp)); 31         for(i=1;i<=k;i++) 32         {
    33             for(x=1;x<=n;x++) 34             {
    35                 if(belong[x]==i) 36                 {
    37                     for(int j=m;j>=w[x];j--) 38                     {
    39                         dp[i][j]=max(dp[i][j],dp[i][j-w[x]]+v[x]); 40                         dp[i][j]=max(dp[i][j],dp[i-1][j-w[x]]+v[x]); 41                     } 42                 } 43             } 44         } 45         int ans=0; 46         for(i=0;i<=m;i++) 47             if(dp[k][i]>ans) 48                 ans=dp[k][i]; 49         if(ans==0) printf("Impossible\n"); 50         else printf("%d\n",ans); 51     } 52     return 0; 53 }