UESTC 1218 Pick The Sticks （dp )

UESTC 1218 Pick The Sticks （dp )

​​一根长为m的长木板和一些小木棒，每一根小木棒有它的长度和价值，这些小木棒要放在长木板上并且每一根小木棒的重心要在长木板上（可以露出一半的长），最大价值是多少。

让人联想到01背包，但是又有些许的不同。

#include #include #include #include using namespace std;const int N=4e3+10;typedef long long LL;LL dp[N][5]; // 0,1,2分别表示露在外面的木棍数量LL a[1010],v[1010];int main(){ //freopen("cin.txt","r",stdin); LL n,t=0,m,len; cin>>n; while(n--){ scanf("%lld%lld",&m,&len); len=len*2; LL ans=0; for(int i=0;i=a[i]/2;j--){ dp[j][1]=max(dp[j-a[i]/2][0]+v[i],dp[j][1]); // outside dp[j][2]=max(dp[j-a[i]/2][1]+v[i],dp[j][2]); // 不放就仍然使用原值 if(j>=a[i]){ dp[j][0]=max(dp[j-a[i]][0]+v[i],dp[j][0]); //inside dp[j][1]=max(dp[j-a[i]][1]+v[i],dp[j][1]); dp[j][2]=max(dp[j-a[i]][2]+v[i],dp[j][2]); } } } for(int i=0;i<3;i++){ ans=max(ans,dp[len][i]); } printf("Case #%lld: %lld\n",++t,ans); } return 0;}

注意：

那个双重循环里的第二层循环如果写成 for(int j=a[i]/2;j<=len;j++) //这种遍历会造成数据污染（滚动数组），除非再开一维。另外，因为输出格式不对，%lld--写成-->%I64d 居然出现了 （Restricted Function on test 1）瞬间惊呆了我。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。