| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
c++一直wa , 转成g++之后才发现re 了 , blocks 数组 因为二进制转换后 不够用了#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int dp[40005]; // dp[i] ==1 则说明 i可以到达 struct block{ int number ; int maxHeight; int height; // number 和 height 可以 合并为一个 总值 } blocks[4005]; int cmp(const block& a , const block& b){ return a.maxHeight<b.maxHeight; } int pow2[30]; int main(){ pow2[0]=1; //记录二进制数 for(int i=1 ; i<30 ; i++) pow2[i]=pow2[i-1]*2; int n; cin>>n; int number , maxHeight ,height; int blockNum=0; for(int i=0 ; i<n ; i++){ cin>>height>>maxHeight>>number; int k=0; while(number){ if(number>pow2[k]){ number-=pow2[k]; blocks[blockNum].height = height; blocks[blockNum].number = pow2[k]; blocks[blockNum].maxHeight = maxHeight; k++; blockNum++; }else{ blocks[blockNum].height = height; blocks[blockNum].number = number; blocks[blockNum].maxHeight = maxHeight; blockNum++; break; } } } sort(blocks , blocks+blockNum , cmp); dp[0]=1; for(int i=0 ; i<blockNum ; i++){ for(int j=40000 ; j>=0 ; j--){ // 状态转移方程 if( j - blocks[i].height * blocks[i].number>=0 && dp [j - blocks[i].height * blocks[i].number ] && j<= blocks[i].maxHeight ) dp[j]=1; } } for(int i=40000 ; i>=0 ; i--){ if(dp[i]){ cout<<i<<endl; break; } } return 0; } //432K 344MS Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator