DP+BIT(복잡성 최적화) UESTC 1217 The Battle of Chibi

2261 단어

제목 전송문
제목: n 길이의 서열을 묻고 길이 m의 상승자 서열을 찾아내는 방안수.
분석: 이 질문은 바로 dp[i][j]=sum(dp[i-1][k])(1<=k<=n,a[k] 
/************************************************
* Author        :Running_Time
* Created Time  :2015/10/21     13:20:36
* File Name     :C.cpp
 ************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
struct BIT  {
    int c[N], SZ;
    void add(int &a, int b) {
        a += b;
        while (a >= MOD)    a -= MOD;
    }
    void init(int n)    {
        memset (c, 0, sizeof (c));
        SZ = n;
    }
    void updata(int i, int x)   {
        while (i <= SZ) {
            add (c[i], x);  i += i & (-i);
        }
    }
    int query(int i)    {
        int ret = 0;
        while (i)   {
            add (ret, c[i]);    i -= i & (-i);
        }
        return ret;
    }
}bit;
int a[N], A[N];
int dp[N][N];

void compress(int n) {
    sort (A, A+n);
    int nn = unique (A, A+n) - A;
    for (int i=0; i

  
전재 대상:https://www.cnblogs.com/Running-Time/p/4923805.html

좋은 웹페이지 즐겨찾기