奇虎360 2017春招真題

1.分金子

A、B兩夥馬賊意外地在一片沙漠中發現了一處金礦，雙方都想獨占金礦，但各自的實力都不足以吞下對方，經過談判後，雙方同意用一個公平的方式來處理這片金礦。處理的規則如下：他們把整個金礦分成n段，由A、B開始輪流從最左端或最右端占據一段，直到分完為止。

馬賊A想提前知道他們能分到多少金子，是以請你幫忙計算他們最後各自擁有多少金子?（兩夥馬賊均會采取對己方有利的政策）

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

int a[505];
int dp[505][505];
int sum[505];

int dfs(int l,int r)
{
    if(l>r) return 0;
    if(dp[l][r]!=-1) return dp[l][r];
    dp[l][r]=sum[r]-sum[l-1]-min(dfs(l+1,r),dfs(l,r-1));
    return dp[l][r];
}

int main()
{
    int t;
    scanf("%d",&t);
    int cas=1;
    while(t--)
    {
        int n;
        scanf("%d",&n);
        memset(dp,-1,sizeof(dp));
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            dp[i][i]=a[i];
            sum[i]=sum[i-1]+a[i];
        }
        int ans1=dfs(1,n);
        int ans2=sum[n]-ans1;
        cout<<"Case #"<<cas++<<": "<<ans1<<" "<<ans2<<endl;
    }
    return 0;
}
           

2.剪氣球串

小明買了一些彩色的氣球用繩子串在一條線上，想要裝飾房間，每個氣球都染上了一種顔色，每個氣球的形狀都是各不相同的。我們用1到9一共9個數字表示不同的顔色，如12345則表示一串5個顔色各不相同的氣球串。但小明希望得到不出現重複顔色的氣球串，那麼現在小明需要将這個氣球串剪成多個較短的氣球串，小明一共有多少種剪法？如原氣球串12345的一種是剪法是剪成12和345兩個氣球串。

注意每種剪法需滿足最後的子串中氣球顔色各不相同（如果滿足該條件，允許不剪，即保留原串）。兩種剪法不同當且僅當存在一個位置，在一種剪法裡剪開了，而在另一種中沒剪開。詳見樣例分析。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

typedef long long LL;

const LL mod = 1e9 + 7;

int a[100005];
LL dp[100005];
int vis[10];

int main()
{
    int n;
    scanf("%d",&n);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    a[0]=0;
    dp[0]=dp[1]=1;
    for(int i=2;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        vis[a[i]]=1;
        for(int j=1;j<=9;j++)
        {
            if(i-j<0) break;
            dp[i]=(dp[i]+dp[i-j])%mod;
            if(vis[a[i-j]]==1) break;
            vis[a[i-j]]=1;
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}