526互联

动态规划专题4

发布时间 2023-12-10 08:28:57作者: Tinx
A.游戏王
 
时间：1s   空间：256M
题目描述
大哈是个游戏王，尽管他的水平一言难尽，但他却总是这样自我称呼。小羽说如果你能把这个游戏通关了，你才算是个真的游戏王。这个游戏一开始你有n个连在一起的颜色块，第i个颜色块的颜色为ai​。如果从i到j的颜色都一样，就说明i到j属于同一个连通块。比如[5,5,5]属于同一个连通块，[4,3,9,9]有3个连通块。游戏开始前大哈可以选择任意一个位置作为起始点，然后开始游戏。游戏的每一轮大哈可以将包含起始点的连通块的颜色变成任意一种其他的颜色。问大哈能将整个数组变成从1到n的连通块所需要的最少回合数。
 
输入格式
第一行一个整数n（1≤n≤5000）
 
第二行n个整数ai​（1≤ai​≤5000）
 
 
 
输出格式
一个整数代表最少回合数
 
 
 

样例输入

4 5 2 2 1
 

 

样例输出

2
 
①n个连在一起的连通块
②选择任意一个起始点开始；包含起始点
 
（1）一段连续的相同元素可以看成一个值
（2）①区间为1    1，1符合一个连通块内。
         ②区间为2的时候{相同时：f[l][r]=f[l+1][r-1]+1；不相同时：f[l][r]=min(f[l+1][r],f[l][r-1])+1}。
 
 
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=5050;
 4 int n,f[N][N],a[N],last,m;
 5 int main(){
 6     cin>>n;
 7     for(int i=1,x;i<=n;i++){
 8         cin>>x;
 9         if(x!=last){
10             a[m++]=x;
11         }
12         last=x;
13     }
14     for(int len=2;len<=m;len++){
15         for(int l=1;l+len-1<=m;l++){
16             int r=l+len-1;
17             if(a[l]==a[r]) f[l][r]=f[l+1][r-1]+1;
18             else f[l][r]=min(f[l+1][r],f[l][r-1])+1;
19         }
20     }
21     cout<<f[1][m];
22     return 0;
23 }
24 
25 编译结果
26 compiled successfully
27 time: 178ms, memory: 58252kb, score: 100, status: Accepted
28 > test 1: time: 0ms, memory: 3372kb, points: 10, status: Accepted
29 > test 2: time: 1ms, memory: 5752kb, points: 10, status: Accepted
30 > test 3: time: 99ms, memory: 58252kb, points: 10, status: Accepted
31 > test 4: time: 0ms, memory: 10596kb, points: 10, status: Accepted
32 > test 5: time: 67ms, memory: 46044kb, points: 10, status: Accepted
33 > test 6: time: 0ms, memory: 8752kb, points: 10, status: Accepted
34 > test 7: time: 2ms, memory: 8676kb, points: 10, status: Accepted
35 > test 8: time: 4ms, memory: 8640kb, points: 10, status: Accepted
36 > test 9: time: 3ms, memory: 8680kb, points: 10, status: Accepted
37 > test 10: time: 2ms, memory: 8372kb, points: 10, status: Accepted

 

B.字符选择

题目描述

Alice 和 Bob 在玩游戏。

给出一个长度为偶数的，非空的且仅含小写字母的字符串 �s。每个玩家还拥有一个初始为空的字符串。

Alice 先手，两名玩家交替行动。在一次行动中，玩家可以取 �s 首或尾字符，将其从 �s 中移除后加入到自己的字符串的 最前面。

当 �s 为空时游戏结束，拥有字典序更小的字符串的玩家获胜。若两名玩家的字符串相等则平局。

若 Alice 和 Bob 都足够聪明，判断谁会取胜，或者游戏为平局。

数据组数 �≤15t≤15，∑∣�∣≤3×103∑∣s∣≤3×103。保证所有输入的 ∣�∣∣s∣ 长度都为偶数。

样例输入1

1 aa

样例输出1

Draw

样例输入2

1 ab

样例输出2

Alice

 

Alice{(l{r,l+1})(max 1);(r{r-1,l})(max 2)}

 

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+10;
string s;
char ar[N];
int f[N][N];
int n;
inline int make(int a,int b,int c){
    if(a!=1) return a;
    return (ar[b]<ar[c]?0:(ar[b]==ar[c]?1:2));
}
inline void solve(){
    cin>>s;
    n=s.size();
    for(int i=0;i<n;i++) ar[i+1]=s[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=3;
        }
    }
    for(int len=2;len<=n;len+=2){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            if(len==2){
                f[l][r]=(ar[l]==ar[r]);
                continue;
            }
            int res=2;
            res=min(res,max(make(f[l+1][r-1],l,r),make(f[l+2][r],l,l+1)));
            res=min(res,max(make(f[l+1][r-1],r,l),make(f[l][r-2],r,r-1)));
            f[l][r]=res;
        }
    }
    if(f[1][n]==0) cout<<"Alice\n";
    else if(f[1][n]==1) cout<<"Draw\n";
    else cout<<"Bob\n";
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

编译结果
compiled successfully
time: 10ms, memory: 9832kb, score: 100, status: Accepted
> test 1: time: 3ms, memory: 9540kb, points: 10, status: Accepted
> test 2: time: 0ms, memory: 7740kb, points: 10, status: Accepted
> test 3: time: 0ms, memory: 9784kb, points: 10, status: Accepted
> test 4: time: 2ms, memory: 9832kb, points: 10, status: Accepted
> test 5: time: 0ms, memory: 9760kb, points: 10, status: Accepted
> test 6: time: 1ms, memory: 7780kb, points: 10, status: Accepted
> test 7: time: 1ms, memory: 8044kb, points: 10, status: Accepted
> test 8: time: 1ms, memory: 7904kb, points: 10, status: Accepted
> test 9: time: 1ms, memory: 8468kb, points: 10, status: Accepted
> test 10: time: 1ms, memory: 7760kb, points: 10, status: Accepted

 

A.游戏王
时间：1s   空间：256M题目描述大哈是个游戏王，尽管他的水平一言难尽，但他却总是这样自我称呼。小羽说如果你能把这个游戏通关了，你才算是个真的游戏王。这个游戏一开始你有n个连在一起的颜色块，第i个颜色块的颜色为ai​。如果从i到j的颜色都一样，就说明i到j属于同一个连通块。比如[5,5,5]属于同一个连通块，[4,3,9,9]有3个连通块。游戏开始前大哈可以选择任意一个位置作为起始点，然后开始游戏。游戏的每一轮大哈可以将包含起始点的连通块的颜色变成任意一种其他的颜色。问大哈能将整个数组变成从1到n的连通块所需要的最少回合数。
输入格式第一行一个整数n（1≤n≤5000）
第二行n个整数ai​（1≤ai​≤5000）
 
输出格式一个整数代表最少回合数


样例输入4 5 2 2 1 样例输出2
①n个连在一起的连通块②选择任意一个起始点开始；包含起始点
（1）一段连续的相同元素可以看成一个值（2）①区间为1    1，1符合一个连通块内。         ②区间为2的时候{相同时：f[l][r]=f[l+1][r-1]+1；不相同时：f[l][r]=min(f[l+1][r],f[l][r-1])+1}。

#include<bits/stdc++.h>using namespace std;const int N=5050;int n,f[N][N],a[N],last,m;int main(){cin>>n;for(int i=1,x;i<=n;i++){cin>>x;if(x!=last){a[m++]=x;}last=x;}for(int len=2;len<=m;len++){for(int l=1;l+len-1<=m;l++){int r=l+len-1;if(a[l]==a[r]) f[l][r]=f[l+1][r-1]+1;else f[l][r]=min(f[l+1][r],f[l][r-1])+1;}}cout<<f[1][m];return 0;}
编译结果compiled successfullytime: 178ms, memory: 58252kb, score: 100, status: Accepted> test 1: time: 0ms, memory: 3372kb, points: 10, status: Accepted> test 2: time: 1ms, memory: 5752kb, points: 10, status: Accepted> test 3: time: 99ms, memory: 58252kb, points: 10, status: Accepted> test 4: time: 0ms, memory: 10596kb, points: 10, status: Accepted> test 5: time: 67ms, memory: 46044kb, points: 10, status: Accepted> test 6: time: 0ms, memory: 8752kb, points: 10, status: Accepted> test 7: time: 2ms, memory: 8676kb, points: 10, status: Accepted> test 8: time: 4ms, memory: 8640kb, points: 10, status: Accepted> test 9: time: 3ms, memory: 8680kb, points: 10, status: Accepted> test 10: time: 2ms, memory: 8372kb, points: 10, status: Accepted