poj 2392 (Space Elevator) 1276 (Cash Machine)变形背包

这道题跟coins很像，看来楼教主的男人八题果然不简单。

进行coins式的背包处理就好了。

2392

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #define max(a,b) ((a)>(b)?(a):(b)) typedef long long ll; using namespace std; const int maxn=41000; struct P { int a,b,c; }p[maxn]; bool cmp( const struct P &a,const struct P&b) { return a.b
       
        dp[j] ) { use[j]=use[j-p[i].a]+1; dp[j]=dp[j-p[i].a]+p[i].a; maxh=max(maxh,dp[j]); } } } cout<
        
         
 
         
1276





 
         

         
#include
          
           
#include
           
             #include
            
              #include
             
               #include
              
                #define max(a,b) ((a)>(b)?(a):(b)) typedef long long ll; using namespace std; const int maxn=10+1000; struct P { int a,c; }p[maxn]; int dp[maxn*1000],use[maxn*1000]; int n,m,T; int K; int main() { while(~scanf("%d",&K)) { int maxh=0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&p[i].c,&p[i].a); memset(dp,-1,sizeof(dp)); dp[0]=0; for(int i=1;i<=n;i++) { memset(use,0,sizeof(use)); for(int j=p[i].a;j<=K;j++) { if( dp[j-p[i].a]!=-1 && use[j-p[i].a]
               
                dp[j] ) { use[j]=use[j-p[i].a]+1; dp[j]=dp[j-p[i].a]+p[i].a; maxh=max(maxh,dp[j]); } } } cout<