1 条题解

  • 1

    没人写题解,就水一篇。

    网站比赛时的我be like:

    第一眼:什么鬼,你家小学组出区间 dp?

    第二眼:似乎可以模拟……

    思路(组织不好语言):可以每次循环就把字符串的第一位挪到最后一位的后面,其它前移保持不变,然后判断要改多少字符,设这是第 ii 次循环,要改 tt 个字符,则花费为 i×A+t×Bi \times A+t \times B,然后打擂台。

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    long long n,a,b;
    int judge(string s){//要改多少字符
    	int times=0;
    	int l=0,r=s.size()-1;
    	while(l<r){
    		if(s[l]!=s[r])	times++;
    		l++;
    		r--;
    	}
    	return times;
    }
    unsigned long long ans=ULONG_MAX;
    int main(){
    	string s;
    	cin>>n>>a>>b>>s;
    	if(judge(s)==0){cout<<0;return 0;}
    	for(int i=0;i<n;i++){//顺序不能反,一定从0开始
    		unsigned long long cost=i*a+judge(s)*b;
    		ans=min(ans,cost);
    		s=s.substr(1)+s[0];
    	}
    	cout<<ans;
    	return 0;
    }
    
    • 1

    信息

    ID
    909
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    25
    已通过
    2
    上传者