B Alice and Bob
?输入输出文件: alice.in/alice.out
?源文件名: alice.cpp/alice.c/alice.pas
? 时间限制: 1s 内存限制: 128M
题目描述
Alice 和 Bob 发明了一个新的游戏。给定一个序列{x0,x1,··· ,xn?1}。Alice得 到一个序列 {a0,a1,··· ,an?1}，其中 ai 表示以 xi 结尾的最长上升子序列的长 度；Bob 得到一个序列 {b0,b1,··· ,bn?1}，其中 bi 表示以 xi 开头的最长下降 子序列的长度。Alice的得分是序列 {a0,a1,··· ,an?1} 的和，Bob的得分是 {b0,b1,··· ,bn?1}的和。 输输输入入入 输入的第一行是 n，第二行是序列{a0,a1,··· ,an?1}。数据保证序列 a 可以由 至少一个 1 到 n 的排列得到。
输出
输出包含一行，表示 Bob
能得到的最高分数。
样例输入1
4 1 2 2 3
样例输出1
5
样例输入2
4 1 1 2
3
样例输出2
5
数据范围 对于 30%
的数据，N ≤ 1000
对于 100% 的数据，N ≤ 10^5
这道题一看到的时候觉得可做，马上写出了一个转移方程 f[i]表示从后往前值为 i 时最长的答案，觉得似乎只能从后面 的 a值小于i的地方转移过来，然后就比SCOIDay1T1简单，用同样的思路加树状数组就出来了。但是后来再检查的时候仔细推了一下，发现有些不对。
对于两个位置p,q(p<q) 如果a[p]>=a[q] 那么x[p]>x[q] ,这一点很显而易见，但是如果a[p]<a[q]并不能推出x[p]<x[q]比如x为1 6 2 5 3 4时a值为1 2 2 3 3 4 a[2]<a[6]但是x[2]>x[6]，所以说有一定问题。我们发现，如果满足a[p]<a[q]&&x[p]>x[q]则一定存在另一个序列从p后面等于a[p]这个值开始，不断累加可以得到，比如a[2]后面a[3]==a[2] ,a[4]==a[3]+1,a[6]==a[4]+1，所以第6个位置可能比第二个位置小
然后就得到了一个暴力的方法，小于的像原来那样弄，大于的N^2来搞，这样子可以得30分
然后想优化，思想上比较麻烦，写起来很简单，直接看代码吧：
1 #include <cstdio> 2 #include <cstdlib> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 int lowbit(int x) {return x&-x;} 7 8 int num[100010]; 9 int n; 10 void change(int data,int pos) 11 { 12 while (pos<=n) 13 { 14 num[pos]=max(num[pos],data); 15 pos+=lowbit(pos); 16 } 17 } 18 19 int getans(int pos) 20 { 21 int ret=0; 22 while (pos>0) 23 { 24 ret=max(ret,num[pos]); 25 pos-=lowbit(pos); 26 } 27 return ret; 28 } 29 30 int a[100010]; 31 int f[100010]; 32 int fself[100010]; 33 int nextc[100010]; 34 int nextb[100010]; 35 int last[100010]; 36 int maxd[100010]; 37 void pre() 38 { 39 for (int i=n;i>=1;--i) 40 { 41 nextc[i]=last[a[i]]; 42 last[a[i]]=i; 43 nextb[i]=last[a[i]+1]; 44 } 45 } 46 47 void trans(int k) 48 { 49 fself[k]=fself[nextb[k]]; 50 fself[k]=max(fself[k],maxd[a[k]]); 51 } 52 53 int getbigans(int k) 54 { 55 return fself[nextc[k]]+1; 56 } 57 58 int viodp() 59 { 60 int ret=0; 61 for (int i=n;i>=1;--i) 62 { 63 f[i]=1; 64 for (int j=i+1;j<=n;++j) 65 { 66 if (a[j]<=a[i]) 67 f[i]=max(f[i],f[j]+1); 68 } 69 int now=a[i]; 70 for (int j=i+1;j<=n;++j) 71 { 72 if (a[j]<=now&&a[j]>a[i]) 73 f[i]=max(f[i],f[j]+1); 74 if (a[j]==now) 75 { 76 now=now+1; 77 } 78 } 79 ret+=f[i]; 80 } 81 // cout<<endl; 82 return ret; 83 } 84 85 long long dp() 86 { 87 long long ret=0; 88 for (int i=n;i>=1;--i) 89 { 90 int f=getans(a[i])+1; 91 f=max(f,getbigans(i)); 92 maxd[a[i]]=max(maxd[a[i]],f); 93 trans(i); 94 change(f,a[i]); 95 ret+=f; 96 } 97 return ret; 98 } 99 100 int main() 101 { 102 freopen ("alice.in","r",stdin); 103 freopen ("alice.out","w",stdout); 104 scanf("%d",&n); 105 for (int i=1;i<=n;++i) 106 { 107 scanf("%d",&a[i]); 108 } 109 if (n<=1000) 110 { 111 cout<<viodp()<<endl; 112 return 0; 113 } 114 pre(); 115 cout<<dp()<<endl; 116 return 0; 117 }
Viodp就是暴力的DP
自己看着理解理解吧。。。其实我觉得这道DP不错，有些意思。似乎其他人写了什么拓扑排序只有50分。
关于TJOI2014的一道题——Alice and Bob,布布扣,bubuko.com
原文：http://www.cnblogs.com/SymenYang/p/3731674.html
