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

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博客 ,格式可能有所偏差。