比赛时，开了大号去做，算了半天发现不会做A，囧。于是跑去看B，发现很水？于是很快敲完了，但是A不会，没敢交。于是去看C，一直找规律啊，后来总算调了出来，看了一下榜，发现还是算了吧，直接去睡觉了。第二天一起床把代码一交，居然A了,发现交的话rating还能涨一点，囧。
B：其实就是求一个最长不下降子序列的长度。注意到数据范围，使用二分的方式求解。
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define debug puts("here")
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define foreach(i,vec) for(unsigned i=0;i<vec.size();i++)
#define pb push_back
#define RD(n) scanf("%d",&n)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define All(vec) vec.begin(),vec.end()
#define MP make_pair
#define PII pair<int,int>
#define PQ priority_queue
#define cmax(x,y) x = max(x,y)
#define cmin(x,y) x = min(x,y)
#define Clear(x) memset(x,0,sizeof(x))
/*
#pragma comment(linker, "/STACK:1024000000,1024000000")
int size = 256 << 20; // 256MB
char *p = (char*)malloc(size) + size;
__asm__("movl %0, %%esp
" :: "r"(p) );
*/
/******** program ********************/
const int MAXN = 100005;
int a[MAXN];
int dp[MAXN];
int q[MAXN];
int n;
void cc(){
int top = 0;
rep1(i,n){
if(top==0||dp[top]<a[i]){
dp[++top] = a[i];
continue;
}
int l = 1 , r = top;
int ans = 1;
while(l<=r){
int mid = (l+r)>>1;
if(dp[mid]<a[i])
l = mid+1;
else{
ans = mid;
r = mid-1;
}
}
dp[ans] = a[i];
}
cout<<top<<endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("sum.in","r",stdin);
//freopen("sum.out","w",stdout);
#endif
while(cin>>n){
rep1(i,n)
RD(a[i]);
cc();
}
return 0;
}
C：注意变与不变的部分。
假设现在有位置：1,2,3,4,5,6
需要填入的数为：1,2,3,4,7,8
则可以分成两个部分：右边的可以匹配任意位置。
位置：1,2,3,4 5,6
数： 1,2,3,4 7,8
1.当左边的数1匹配上左边时，不妨假设1-2，则左边消除了两个，右边增加一个：数2可以匹配其他的所有位置
2.当左边的数1匹配上右边时，不妨假设1-5，则左边消除了一个，右边数目不变（消除了5，添加了1）
3.当右边的数7匹配上左边时，不妨假设7-1，则左边消除了一个，右边数目不变（消除了7，添加了1）
4.当右边的数7匹配上右边时，不妨假设7-5，则左边不变，右边数目减少一个
所以可以dp，dp[i][j]表示左边有i个，右边有j个时的方案数。
1.当i=0时，为p[j]（p[j]表示j的排列）
2.当i=1时，左边任意匹配右边一位，右边数目不变，因此方案数为为p[j]*j。
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define debug puts("here")
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define foreach(i,vec) for(unsigned i=0;i<vec.size();i++)
#define pb push_back
#define RD(n) scanf("%d",&n)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define All(vec) vec.begin(),vec.end()
#define MP make_pair
#define PII pair<int,int>
#define PQ priority_queue
#define cmax(x,y) x = max(x,y)
#define cmin(x,y) x = min(x,y)
#define Clear(x) memset(x,0,sizeof(x))
/*
#pragma comment(linker, "/STACK:1024000000,1024000000")
int size = 256 << 20; // 256MB
char *p = (char*)malloc(size) + size;
__asm__("movl %0, %%esp
" :: "r"(p) );
*/
/******** program ********************/
const int MAXN = 2005;
const int MOD = 1e9+7;
ll dp[MAXN][MAXN];
int a[MAXN],n;
bool use[MAXN];
ll p[MAXN];
ll dfs(int x,int y,int res){
if(res<=0) return p[y];
if(x==1)return p[y]*y%MOD;
if(x==0)return p[y];
if(~dp[x][y])return dp[x][y];
ll tmp = (x-1);
tmp *= dfs(x-2,y+1,res-2);
tmp += dfs(x-1,y,res-1)*y;
return dp[x][y] = tmp%MOD;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("sum.in","r",stdin);
//freopen("sum.out","w",stdout);
#endif
p[0] = p[1] = 1;
for(int i=2;i<MAXN;i++)
p[i] = p[i-1]*i%MOD;
while(cin>>n){
Clear(use);
rep1(i,n){
RD(a[i]);
if(~a[i])
use[ a[i] ] = true;
}
int x = 0 , y = 0;
rep1(i,n){
if(a[i]==-1){
if(use[i])y ++;
else x ++;
}
}
memset(dp,-1,sizeof(dp));
cout<<dfs(x,y,x+y)<<endl;
}
return 0;
}