2020牛客國慶集訓派對day4(補題)

2020牛客國慶集訓派對day4

B
題意：
  題意：求最長等差序列的長度。

DP:攤派了我講不明白,參考下這兩篇部落格吧(捂臉)
傳送門1
傳送門2

#include<cstdio>
#include<iostream>
#include<queue>
#include<set>
#include<algorithm>
#include <cstring>
#include <string>

using namespace std;

typedef long long ll;

const int maxn  = 5e3 + 7;

int arr[maxn];
int dp[maxn][maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    int ans = 0;
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>arr[i];
    sort(arr + 1, arr + 1 + n);
    for(int i = 1; i <= n; i++){
        int l = i - 1;//向左找
        for(int j = i + 1; j <= n; j++){
            dp[i][j] = 2;
            int dis = arr[j] - arr[i];
            while(l > 0 && dis > arr[i] - arr[l]) l--;
            if(l > 0 && dis == arr[i] - arr[l]) dp[i][j] = dp[l][i] + 1;
            ans = max(ans,dp[i][j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

J
題意：
  右邊有n個數，從1到n， 現在把他們之間的空格去掉得到左邊的字串， 現在給出左邊的字串，求右邊分隔開的數列。

先計算n的值，如果字串長度<= 9，那麼所有字元應該要獨自輸出，字串長度> 9 說明存在兩位的數，那麼n = (lenth - 9) / 2 + 9 然後用dfs列舉所有可能序列，當前一步可以把它自己當作一個數位也可以與後一位結合成一個兩位數，再找到一個之後不再繼續尋找，其實我剛開始感覺dfs會爆，因為完全跑完複雜度會是 O(2ⁿ)，但是一想，只需要找第一個滿足條件的序列就可以，而且還有剪枝，一般是不會爆

程式碼

#include<cstdio>
#include<iostream>
#include<queue>
#include<set>
#include<algorithm>
#include <cstring>
#include <string>

using namespace std;

typedef long long ll;

const int maxn  = 250000 + 10;

bool vis[51] , flag;
char p[100];
int arr[51],cnt,n,len;

void DFS(int i )
{
    if(flag)    return ;
    if(i == len){
        for(int i = 0; i < n; i++)  printf("%d%c",arr[i], i == n - 1? '\n' : ' ');
        flag =true;
    }
    if(i == len - 1){
        int x = p[i] - '0';
        if(!vis[x] && x <= n){
            vis[x] = true;
            arr[cnt++] = x;
            DFS(i + 1);
            vis[x] = false;
            cnt--;
        }
    }
    else{
        int x = p[i] - '0';
        if(!vis[x] && x <= n){
            vis[x] = true;
            arr[cnt++] = x;
            DFS(i + 1);
            vis[x] = false;
            cnt--;
        }
        x = (p[i] - '0') * 10 + p[i + 1] - '0';
        if(!vis[x] && x <= n){
            vis[x] = true;
            arr[cnt++] = x;
            DFS(i + 2);
            vis[x] = false;
            cnt--;
        } 
    }
}

int main()
{
    //std::ios::sync_with_stdio(false);
    scanf("%s",p);
    len = strlen(p);
    if(len < 10)   for(int i = 0; i < len; i++) printf("%c%c",p[i],i == len - 1? '\n' : ' ');
    else{
        n = (len - 9) / 2+ 9;
        DFS(0);
    }  
    return 0;
}