状态题目:低价购买
题目编号:456-低价购买 查看该题
状态: Unaccepted
测评机： Xeost[5]
得分： 80分
提交日期： 2009-9-20 20:02:00
有效耗时： 405毫秒
测试结果1: 通过本测试点|有效耗时46ms
测试结果2: 通过本测试点|有效耗时47ms
测试结果3: 通过本测试点|有效耗时47ms
测试结果4: 通过本测试点|有效耗时47ms
测试结果5: 通过本测试点|有效耗时46ms
测试结果6: 通过本测试点|有效耗时47ms
测试结果7: 通过本测试点|有效耗时47ms
测试结果8: 测试结果错误.错误结果为:59 152064
正确结果应为:59 532224
测试结果9: 通过本测试点|有效耗时78ms
测试结果10: 测试结果错误.错误结果为:2730 98304
正确结果应为:2730 196608
#include<iostream>
using namespace std；
int price[30002],dp[2][30002]；
bool used[65536]；
int main (void){
int n；
cin>>n；
for (int i=1；i<=n；++i) cin>>price[i]；
price[0]=0x7fffffff；
price[n+1]=-0x7fffffff；
dp[1][0]=1；
for (int i=1；i<=n+1；++i){
for (int j=0；j<i；++j){
if (price[i]<price[j]&&dp[0][i]<dp[0][j]+1) dp[0][i]=dp[0][j]+1；
if (j!=0&&j!=n+1) used[price[j]]=false；
}
if (dp[0][i]==0) dp[0][i]=1；
for (int j=0；j<i；++j){
if (price[i]<price[j]&&dp[0][i]==dp[0][j]+1&&((j==0||j==n+1)||!used[price[j]])){
dp[1][i]+=dp[1][j]；
if (j!=0) used[price[j]]=true；
}
}
}
cout<<dp[0][n+1]-1<<" "<<dp[1][n+1]<<endl；
// while (1)；
return 0；
}