線性DP, 笨得WA了10次才AC,而且高精度加法還是借用的别人的,自己的壓位高精度大數算的好奇怪。。。
本題的重點在于第二問的判重。可以證明,對于相同price的i, j(i<j),應該選擇j,因為j包含i的所有情況。
那麼怎麼判斷某個price是待計算的i前面的最後一個那個j呢,這裡我實在太挫沒有思路。
後來參考了别人的做法,我們可以給每一個j構造一個next指針指向下一個相同數字的下标,如果這個下标>i那麼就表明j是最後一個。
然後就很簡單了,把所有的最後一個加起來就行了。不過本題要使用高精度算法,總時間複雜度為O(N 2)。
Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 5896 KB]
Test 2: TEST OK [0.011 secs, 5896 KB]
Test 3: TEST OK [0.011 secs, 5896 KB]
Test 4: TEST OK [0.011 secs, 5896 KB]
Test 5: TEST OK [0.011 secs, 5896 KB]
Test 6: TEST OK [0.022 secs, 5896 KB]
Test 7: TEST OK [0.032 secs, 5896 KB]
Test 8: TEST OK [0.011 secs, 5896 KB]
Test 9: TEST OK [0.065 secs, 5896 KB]
Test 10: TEST OK [0.248 secs, 5896 KB]
All tests OK.
Your program ('buylow') produced all correct answers! This is your submission #11 for this problem. Congratulations!
1 #include <iostream>
2 #include <iomanip>
3 #include <cstring>
4 #include <cstdio>
5 using namespace std;
6
7 int N, price[5001];
8 int eqn[5001];
9
10 int dp[5001];
11
12 struct bign
13 {
14 char n[500];
15 int len;
16 bign():len(1)
17 {
18 memset(n,0,sizeof(n));
19 }
20 void operator = (const int v)
21 {
22 len = 1;
23 n[0] = v;
24 }
25
26 void operator += (const bign &rhs)
27 {
28 if(rhs.len>len)
29 len=rhs.len;
30 for(int i=0;i<len;++i)
31 {
32 n[i]+=rhs.n[i];
33 if(n[i]>9)
34 {
35 ++n[i+1];
36 n[i]-=10;
37 }
38 }
39 if(n[len])
40 ++len;
41 }
42 void print()
43 {
44 for(int i=len-1;i>=0;--i)
45 cout << (int)n[i];
46 }
47 }dp2[5001];
48
49 int main(void)
50 {
51 freopen("buylow.in", "r", stdin);
52 freopen("buylow.out", "w", stdout);
53 int i, m;
54
55 cin >> N;
56 for(i=0; i<N; ++i) cin >> price[i];
57 N++; // 增加一個超級節點, price[supernode] = 0;
58
59 for(i=0; i<N-1; ++i) {
60 int j;
61 for(j=i+1; j<N; ++j)
62 if (price[j] == price[i]) {
63 eqn[i] = j;
64 break;
65 }
66 if (j >= N) eqn[i] = N;
67 }
68 eqn[N-1] = N;
69
70 for(i=0; i<N; ++i) {
71 dp[i] = 1;
72 dp2[i] = 1;
73 int j;
74 for(j=0; j<i; ++j) {
75 if (price[i] < price[j]) {
76 if (eqn[j] > i) {
77 const int k = dp[j] + 1;
78 if (k > dp[i]) {
79 dp[i] = k;
80 dp2[i] = dp2[j];
81 } else if (k == dp[i])
82 dp2[i] += dp2[j];
83 }
84 }
85 }
86 }
87 cout << dp[N-1] - 1 << ' ';
88 dp2[N-1].print();
89 cout << endl;
90
91 return 0;
92 }
2014/5/20更新:
終于用上自己的高精度了,效率貌似還可以。
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.008 secs, 5400 KB]
Test 2: TEST OK [0.011 secs, 5400 KB]
Test 3: TEST OK [0.008 secs, 5400 KB]
Test 4: TEST OK [0.008 secs, 5400 KB]
Test 5: TEST OK [0.014 secs, 5400 KB]
Test 6: TEST OK [0.024 secs, 5400 KB]
Test 7: TEST OK [0.022 secs, 5400 KB]
Test 8: TEST OK [0.024 secs, 5400 KB]
Test 9: TEST OK [0.054 secs, 5400 KB]
Test 10: TEST OK [0.270 secs, 5400 KB]
All tests OK.
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdio>
using namespace std;
int N, price[5001];
int eqn[5001];
int dp[5001];
#define min(a,b) ((a)>(b)?(b):(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define BIGNUM_LL 100
#define BIGNUM_BL "4"
#define BIGNUM_MOD 10000UL
typedef typeof(BIGNUM_MOD) bignum_block;
struct bignum {
unsigned len;
bignum_block blks[BIGNUM_LL];
bignum() {blks[0]=0, len=1;}
bignum(unsigned num) {
len = 0;
while(num) {
blks[len++] = num % BIGNUM_MOD;
num /= BIGNUM_MOD;
}
}
void operator += (bignum &b) {
int i;
bignum_block carry;
i = len; do blks[i++] = 0; while(i<=b.len);
carry = i = 0;
for(; i<b.len; ++i) {
blks[i] += b.blks[i];
blks[i+1] += blks[i] / BIGNUM_MOD;
blks[i] %= BIGNUM_MOD;
}
for(; i<len; ++i) {
blks[i+1] += blks[i] / BIGNUM_MOD;
blks[i] %= BIGNUM_MOD;
}
len = i + (blks[i] > 0);
}
void print() {
printf("%d", blks[len-1]);
for(int i=len-1; i--; )
printf("%0" BIGNUM_BL "d", blks[i]);
}
}dp2[5001];
int main(void)
{
freopen("buylow.in", "r", stdin);
freopen("buylow.out", "w", stdout);
int i, m;
cin >> N;
for(i=0; i<N; ++i) cin >> price[i];
N++; // 增加一個超級節點, price[supernode] = 0;
for(i=0; i<N-1; ++i) {
int j;
for(j=i+1; j<N; ++j)
if (price[j] == price[i]) {
eqn[i] = j;
break;
}
if (j >= N) eqn[i] = N;
}
eqn[N-1] = N;
for(i=0; i<N; ++i) {
dp[i] = 1;
dp2[i] = 1;
int j;
for(j=0; j<i; ++j) {
if (price[i] < price[j]) {
if (eqn[j] > i) {
const int k = dp[j] + 1;
if (k > dp[i]) {
dp[i] = k;
dp2[i] = dp2[j];
} else if (k == dp[i])
dp2[i] += dp2[j];
}
}
}
}
cout << dp[N-1] - 1 << ' ';
dp2[N-1].print();
cout << endl;
return 0;
}
轉載于:https://www.cnblogs.com/e0e1e/p/usaco_buylow.html