省赛选拔赛——个人赛第四场

发表于 分类于 Disqus：

Rank 6。
就出了一道题，还CE了一次。然后剩下的时间就一直不知道在干什么，总是来回换题想，没看出来D题是个DP，当时仔细想想，肯定能出。

B：POJ 3278
简单BFS，一开始没写cstring头文件CE了。23分钟AC。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=100010;
int n,k,d[maxn*2];
queue<int> q;
int main(){
    while(cin>>n>>k){
        memset(d,-1,sizeof(d));
        while(!q.empty()) q.pop();
        q.push(n);
        d[n]=0;
        while(!q.empty()){
            if(d[k]!=-1) break;
            int cur=q.front();q.pop();
            if(cur&&d[cur-1]==-1) q.push(cur-1),d[cur-1]=d[cur]+1;
            if(cur<2*maxn-1&&d[cur+1]==-1) q.push(cur+1),d[cur+1]=d[cur]+1;
            if(cur*2<200000&&d[cur*2]==-1) q.push(cur*2),d[cur*2]=d[cur]+1;
        }
        cout<<d[k]<<endl;
    }
    return 0;
}

D：POJ 3280
当时没看出来是道DP，赛后补的。
状态转移方程：
d(i,j)=min(d(i+1,j)+min(a[i].add,a[i].del),d(i,j-1)+min(a[j].add,a[j].del))
递推边界：i≥j时，d(i,j)=0
特殊情况：s[i]=s[j]时，d(i,j)=d(i+1,j-1)
另外，对每个字符来说，删除和添加是等价的，所以只需要存添加和删除的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2010;
const int inf=0x3f3f3f3f;
char s[maxn];
int d[maxn][maxn],a[27];
int dp(int l,int r){
    if(l>=r) return 0;
    int &k=d[l][r];
    if(k!=inf) return k;
    if(s[l]==s[r]) return k=dp(l+1,r-1);
    return k=min(dp(l,r-1)+a[s[r]-'a'],dp(l+1,r)+a[s[l]-'a']);
}
int main(){
    int n,len;
    while(~scanf("%d%d",&n,&len)){
        memset(a,0,sizeof(a));
        memset(d,0x3f,sizeof(d));
        scanf("%s",s);
        for(int i=0;i<n;++i){
            getchar();
            int c=getchar(),t1,t2;
            scanf("%d%d",&t1,&t2);
            a[c-'a']=min(t1,t2);
        }
        printf("%d\n",dp(0,len-1));
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章