2013
12-23

# Grocery store

A cashier in a grocery store seems to have difficulty in distinguishing the multiplication symbol and the addition symbol. To make things easier for him, you want to buy goods in such a way that the product of their prices is the same as the sum of their prices.

Of course, if you buy only one item, this is always true. With two items and three items, it still seems quite a boring task to you, so now you are interested in finding possible prices of four items such that the sum of the four prices is equal to the product of the four prices. You should consider the prices are in � with two digits after the decimal point. Obviously, each product costs at least one cent.

This problem has no input.

Print all solutions which have a sum of the four items of at most 20.00 �. For each solution, print one line with the prices of the four items in non-decreasing order, with one space character between them. You may print the solutions in any order, but make sure to print each solution only once.

0.50 1.00 2.50 16.00
1.25 1.60 1.75 1.84
1.25 1.40 1.86 2.00
...

dp[i] 记录了在i之前且在i位置上的最大上升序列和，dp[i]等于前面a[j]<a[i]且dp[j]值的最大与a[i]的和

#include<stdio.h>
__int64 dp[1010],maxn,t;
int a[1010];
int main()
{
int n,i,j;
while(scanf("%d",&n)&&n)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
dp[0]=a[0];t=0;
for(i=1;i<n;i++)
{
maxn=0;
for(j=0;j<i;j++)
if(a[j]<a[i]&&dp[j]>maxn) maxn=dp[j];
dp[i]=a[i]+maxn;
t=t>dp[i]?t:dp[i];
}
printf("%I64d\n",t);
}
return 0;
}


1. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。