HDU-1248 寒冰王座 完全背包

很典型的完全背包，也可以暴力跑一下

350可以分成150+200，200可以分成150+50，所以，先%150，再看看剩下的有多少50，如果比之前的150还多，那就减去150个数*50，如果少，直接%50.

#include <bits/stdc++.h>
using namespace std;
const int N=100007;
int t;
int x;
int main() {cin>>t;while(t--) {cin>>x;int temp1=x/150;x%=150;int temp2=x/50;if(temp2<=temp1) {x%=50;} else {x-=50*temp1;}cout<<x<<endl;}return 0;
}

完全背包解法

#include <bits/stdc++.h>
using namespace std;
const int N=100007;
int t;
int m;
int cost[4]={0,150,350,200};
int dp[N];
int main() {cin>>t;while(t--) {memset(dp,0,sizeof dp);cin>>m;for(int i=1;i<=3;i++){for(int j=cost[i];j<=m;j++){dp[j]=max(dp[j],dp[j-cost[i]]+cost[i]);}}printf("%d\n",m-dp[m]);}return 0;
}