T1 宝物筛选（P1776）
未优化，当成多重背包做。
#include <iostream>
#include <stdio.h>
using namespace std;
int v[1005],w[1005],s[1005],dp[1005];
int main(){
freopen("P1776_4.in","r",stdin);
int N,V;
cin>>N>>V;
for(int i=1;i<=N;i++){
cin>>w[i]>>v[i]>>s[i];
}
for(int i=1;i<=N;i++){
for(int k=V;k>=1;k--){
for(int l=0;l<=s[i]&&l*v[i]<=k;l++){
cout<<k<<' '<<k-l*v[i]<<' ';
dp[k]=max(dp[k],dp[k-l*v[i]]+l*w[i]);
}
}
}
cout<<dp[V];
return 0;
}二进制优化后（节省了大量空间）
#include <iostream>
#include <stdio.h>
using namespace std;
const int maxx=1e7+5;
int N,V;
int v[12005],w[12006],dp[maxx];
int main(){
// freopen("P1776_4.in","r",stdin);
cin>>N>>V;
int count=0;
//分成2^0(1),2^1(2),2^2(4),2^3(8)...余数组。
//O(n^3)->O(n^2logS）
for(int i=1;i<=N;++i){
int z,x,c;
cin>>z>>x>>c;
for(int k=1;k<=c;k*=2){
count++;
v[count]=x*k;//fu gai.?
w[count]=z*k;
c-=k;
}
if(c>0){
count++;
v[count]=x*c;
w[count]=z*c;
}
}
//拿1024次苹果或者拿10次。（7次？
for(int i=1;i<=count;++i){
for(int k=V;k>=1;k--){
if(k>=v[i])
dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
}
}
cout<<dp[V];
return 0;
}T2 尴尬的数字（P1555）
#include <iostream>
using namespace std;
string a,b;
int cvs(string x){
int yu,temp=0;
for(int i=0;i<x.length();i++){
yu=x[i]-'0';
temp*=10;
temp+=yu;
}
return temp;
}//转换数据类型
string er_shi(string x){
int len=x.length(),baka;
int i=0;
if(x[i]!='0')
baka=x[0]-'0';
else{
baka=x[1]-'0';
i++;
}
i++;
for(;i<len;i++){
baka*=2;
baka+=x[i]-'0';
}
string back;
char temp;
while(baka){
temp=(baka%10)+'0';
back=temp+back;
baka/=10;
}
return back;
}//二进制转十进制
string shi_san(string x){
string back;
int num=cvs(x);//
int yu;
char temp;
while(num){
yu=num%3;
temp=yu+'0';
back=temp+back;
num/=3;
}
return back;
}//十进制转三进制
bool cmp(string x){
if(x.length()!=b.length())
return false;
int cnt=0;
for(int i=0;i<b.length();i++){
if(x[i]!=b[i])
cnt++;
}
if(cnt==1) return true;
return false;
}//判断函数
void change(int x){
if(a[x]=='1') a[x]='0';
else a[x]='1';
}
int main(){
cin>>a>>b;
for(int i=0;i<a.length();i++){
if(i==0){
change(i);
}
else{
change(i-1);
change(i);
}//更换数字
//此时是二进制字符串
int ans=-1;
ans=cvs(er_shi(a));//保存答案
if(cmp(shi_san(er_shi(a)))){
cout<<ans;
return 0;
}
else continue;
}
return 0;
}T3 小卡和质数（P8845）
#include <iostream>
int main(){
int t,a,b;
std::cin>>t;
while(t--){
std::cin>>a>>b;
if((a==1&&b==2)||(a==2&&b==1)) std::cout<<"Yes"<<std::endl;
else std::cout<<"No"<<std::endl;
}
return 0;
}