题目链接：
codeforces 366C
题目大意：
给出n个物品，有两个属性，问最后第一个属性的总和是第二个属性的k倍的时候，，第一个属性最大是多少。
题目分析：我们将物品做一个变形，重量为a[i]-b[i]*k,收益是a，那么我们只需要对重量为正的做一遍背包，对质量为负的取绝对值做一遍背包，然后重量相等的背包的收益之和就是当前重量下的最大收益. AC代码：;int dp[MAX*MAX],dd[MAX*MAX];int n,k,a[MAX],b[MAX],c[MAX];int main ( ){while ( ~scanf ( “%d%d” , &n , &k ) ){for ( int i = 0 ; i < n ; i++ )scanf ( “%d” , &a[i] );for ( int i = 0 ; i < n ; i++ )scanf ( “%d” , &b[i] );for ( int i = 0 ; i < n ; i++ )c[i] = a[i]-b[i]*k;memset ( dp , -0x3f , sizeof ( dp ) );memset ( dd , -0x3f , sizeof ( dd ) );dp[0] = dd[0] = 0;for ( int i = 0 ; i < n ; i++ )if ( c[i] >= 0 )for ( int j = 10000 ; j >= c[i] ; j– )dp[j] = max ( dp[j-c[i]]+a[i] , dp[j] );for ( int i = 0 ; i < n ; i++ )if ( c[i] < 0 ){c[i] = -c[i];for ( int j = 10000 ; j >= c[i] ; j– )dd[j] = max ( dd[j-c[i]]+a[i] , dd[j] );}int ans = -1;for ( int i = 0; i <= 10000 ; i++ ){if ( dd[i] == 0 && dp[i] == 0 )continue;ans = max ( ans , dp[i]+dd[i] );}printf ( “%d\n” , ans );}}
穷则思变，差则思勤！没有比人更高的山没有比脚更长的路。
