状态题目:低价购买
题目编号: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;
}