NOIP2005复赛 普及组答案

你叫我砸说呢？
一二题不说。。
第三题用动态规划。。
O【M】表示前M种药材的最大价值。
P【M】表示前M种药材的总时间
A【M】T表示第M种时间
A【M】M表是第M种价值
方程是
O[M]=O[M-1]+A[M]M;T-P[M-1]>=A[M]T
O[M]=Max(O[M-1],A[M]M) T-P[M-1]

只有T1-T3的答案，这些答案是我自己在洛谷上OJ测试过的，都是100分。

T1：
#include
using namespace std;
int main(){
int shuliang=0,taotao,apple[11];
for(int i=1;i<=10;i++)
cin>>apple[i];
cin>>taotao;

taotao+=30;
for(int j=1;j<=10;j++) { if(taotao>=apple[j])
shuliang+=1;
} printf("%d",shuliang);
return 0;
}
T2:
#include
#include
using namespace std;
int l,m,start,end,sum=0;
bool a[10005];
int main()
{
std::cin>>l>>m;
for(int i=1;i<=m;i++)
{
std::cin>>start>>end;
for(int j=start;j<=end;j++)a[j]=true;
}
for(int i=0;i<=10005;i++)
{
if(a[i]==true)sum++;
}
std::cout<system("pause");
return 0;
}
T3:
#include
#include
using namespace std;
int w[30],v[30],f[50000];
int n,m;
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
if(j>=v[i])
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
}
cout<return 0;
}

3题：这个就是0-1背包问题
可以用枚举、递归的策略。
每种只有两种状态——采、不采