对局匹配-白红宇

对局匹配

阅读量：4647 次

发布时间：2019-06-09

本文共 1833 字，大约阅读时间需要 6 分钟。

刚开始直接拿set录数据做，以为是个水题，没想到WA了，只得了12分

WA代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #define I scanf#define OL puts#define O printf#define F(a,b,c) for(a=b;a
                 
                  =0;a--)#define LEN 3000#define MAX 0x06FFFFFF#define V vector
                  
                   using namespace std;int main(){// freopen("D:/CbWorkspace/blue_bridge/对局匹配.txt","r",stdin); int N,K,i,t,ans=0; set
                   
                     s; I("%d %d",&N,&K) ; FF(i,N){ I("%d",&t); if(s.find(t)==s.end()){ s.insert(t+K); s.insert(t-K); ans++; } } printf("%d\n",ans); return 0;}

View Code

看了，终于知道原来是dp。只要思路对，一切都不是问题。

搬运自大佬博客：

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define MAX_SCORE 100000const int maxn = 100000 + 5;int cnt[MAX_SCORE+5], val[maxn], dp[maxn];int n, k;int main() {    while(scanf("%d%d", &n, &k) == 2) {        memset(cnt, 0, sizeof(cnt));        int score, ans = 0;        for(int i = 1; i <= n; i++) {            scanf("%d", &score);            cnt[score]++;        }        //特殊处理k=0的情况        if(k == 0) {            for(int i = 0; i <= MAX_SCORE; i++) {                if(cnt[i]) ans++;            }        }         else {            for(int i = 0; i < k; i++) {                int m = 0;                for(int j = i; j <= MAX_SCORE; j+=k) {                    val[m++] = cnt[j];                }                dp[0] = val[0];                for(int j = 1; j < m; j++) {                    if(j == 1) dp[j] = max(dp[0], val[j]);                    else dp[j] = max(dp[j-2] + val[j], dp[j-1]);                }                ans += dp[m-1];            }        }        printf("%d\n", ans);    }    return 0;}