【OI练习】柯南购物

【OI练习】柯南购物

Description

　　话说柯南开完锁后，本想继续往里走，但是却接到一个电话，原来小哀打电话叫柯南去买衣服（寒），柯南来到步行街，发现衣服就如同它的价格一样漂亮（暴寒），柯南自然不想买这么贵的衣服，他想从买到的衣服总是比上一件便宜，但他又想小哀开心，于是他想尽量买到最多的衣服。你能帮帮他吗？ 　　注：步行街从头到尾有n件商品，每件商品只有一件，柯南不能回头购买。 　　（又及：到后来，柯南进入OIBH总部后，才发现是12+5鼓动了小哀叫柯南买衣服，并且柯南看到12+5时12+5中的鱼牛正拿着个手机阴笑着，柯南一听，是小哀……于是，柯南侦察OIBH组织总部的计划完全失败，下一次又是什么呢？）

　　 Input

　　输入第一行是n（1<=n<=3000），表示步行街上里有n件衣服，以下n行是步行街每件商品的价格，按顺序从头到尾。

　　 Output

　　输出第一行是柯南能购买的最多的商品数，接着是一个空格，再接着是柯南购买商品的方案数除以10000的余数。

　　 Sample Input

12 68 69 54 64 68 64 70 67 78 62 98 87

Sample Output

4 2

Hint

注意：本题的方案数指不同的方案数，即 3 2 2 1 的答案应该是 2 1 而不是 2 2

题目分析

经典DP问题LIS的变形 本题求最多能购买的商品数，因为购买的商品价格必须一件比一件低，即是求价格序列的最长下降子序列。 第二问的最多不同方案数，只需在求最长下降子序列过程中，记录不同路径数即可。对于相同值（价格），只取倒序计算下的第一个，其他参考注释。 另外计算求和过程中，应边累加边求模，否则数据会溢出导致错解。 #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<sstream> using namespace std; int dp[5001]; int a[5001]; int num[5001]; int main() { int n; cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } for(int i=0;i<=n;i++) { num[i]=1; int tmp=1<<30; for(int j = i-1; j>=0;j--) if(a[j]>a[i]) { if(dp[j]>= dp[i]) { tmp=a[j]; dp[i]=dp[j]+1;//最长下降子序列 num[i]=num[j];//路径相同，方案数即相同 } else if (dp[j]+1 == dp[i]&& a[j]< tmp)//从i前面不同的点到达i点； { //如果a[j]> tmp则最长下降子序列的长度就要增加1. //如果a[j]== tmp 就重复了，需要排除． tmp = a[j]; num[i]=(num[i]+num[j])%10000; } } } cout<<dp[n]<<" "<<num[n]%10000<<endl; }