UPC-遊戲智商+ 路标 （動态規劃+DFS）

都是細節處理，就直接放在一篇部落格裡了

遊戲智商

時間限制: 1 Sec 記憶體限制: 128 MB

[送出] [狀态]

題目描述

熊的智商高還是猴子的智商高，這或許是一個很難考究的問題。故事裡，吉吉國王一直标榜自己是最聰明最偉大的猴子國王，他的毛毛也是這麼堅信。而我們的熊大和熊二卻一直相信他們熊熊才是最聰明的。于是，在導遊光頭強的建議下，他們決定來一場 pk。

Pk 的内容是這樣的，有 n 個格子，每個格子從左到右的編号依次是 1 到 n（編号也是位置)，每個格子上都有不同美味值的水果（猴子們和熊們都很喜歡吃水果，是以水果對他們來說很有吸引力）。他們從位置 0 開始出發，手上有 AB 兩種卡片，A 卡有 na 張，B 卡片有nb 張。每次他們可以用掉一張卡片，然後往前跳若幹格，跳的格子數就是卡片上的數字。每跳到一個格子上，就可以吃掉對應格子裡面的水果，獲得水果的美味值。當然了，我們會保證當卡片用完的時候，一定剛好跳到第 n 個格子上。卡片一定要用完，不能有剩餘。

遊戲的結果就是在相同的情況下，誰能獲得的水果美味值總和最大。熊熊們想要赢得這個比賽，于是熊二請求你的幫助。如果你可以幫助他算出最大值，他甚至可以把他最心愛的蜂蜜分享給你。

輸入

輸入第一行是3個整數n，na，nb,va,vb，n表示格子的總數，na表示A種卡片的數量，nb表示B種卡片的數量，va表示A種卡片上的數，vb表示B種卡片上的數。保證n一定等于nava+nbvb。

接下來n個整數，表示每個格子上水果的美味值，注意美味值有可能是負數。

輸出

輸出隻有一行一個整數，表示卡片用完的時候，最多可以得到的美味值總和。

樣例輸入 Copy

3 1 1 2 1

1 2 3

樣例輸出 Copy

5

提示

共計有20個測試點。

對于第1-6個測試點，保證na=1,nb<=200，美味值都是小于等于10000的正整數。

對于第7-12個測試點，保證1<=na,nb<=12，美味值的絕對值小于等于10000。

對于100%的資料，保證1<=n<=20000,1<=na,nb<=2000,1<=va,vb<=5，va不等于vb，美味值的絕對值不超過1000000。

思路：

dp[i][j]表示用了i張A卡片和j張B卡片所擷取的美味值的最大值，狀态轉移方程：

[i][j]=max(dp[i][j],dp[i-1][j]+a[i*va+j*vb]);
 dp[i][j]=max(dp[i][j],dp[i][j-1]+a[i*va+j*vb]);      

#pragma
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define
#define
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}
const int maxn=2010;
ll dp[maxn][maxn];
///dp[i][j]表示用了i張A卡片和j張B卡片所擷取的美味值的最大值
ll n,na,nb,va,vb;
ll a[20010];
void AC(){
    n=read();na=read();nb=read();va=read();vb=read();
    for(ll i=1;i<=n;i++) a[i]=read();
    for(ll i=0;i<=na;i++){
        for(ll j=0;j<=nb;j++){
            if(i>=1) dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i*va+j*vb]);
            if(j>=1) dp[i][j]=max(dp[i][j],dp[i][j-1]+a[i*va+j*vb]);
        }
    }
    out(dp[na][nb]);
}
int main(){
    AC();
    return 0;
}      

路标

#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int maxx=-1;
int g[maxn][maxn],col[maxn];
int n,m;
///1是白2是黑
bool check(int u){
    for(int i=1;i<=n;i++)
        if(g[u][i]||g[i][u]){
            if(col[i]==1&&col[u]==1) return 0;
        }
    return 1;
}
void dfs(int u){
    if(u==n+1){
        int tot=0;
        for(int i=1;i<=n;i++) if(col[i]==1) tot++;
        maxx=max(maxx,tot);
    }
    else{
        for(int i=1;i<=2;i++){
            col[u]=i;
            if(check(u)) dfs(u+1);
            col[u]=0;
        }
    }
}
void AC(){
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        g[x][y]=g[y][x]=1;
    }
    dfs(1);
    cout<<maxx<<endl;
}
int main(){
    AC();
    return 0;
}