E. Divisibility by 25
能被25整除的充要条件就是末两位是00，25，50，75。如果没有过程中不出现前导0这一限制，显然对每种情况，贪心取尽量低位即可。本题的关键就在于如何满足这个条件，首先有个”显然”的方法：讨论。。。然后会发现情况太多，过于复杂。所以，我们只好从交换本身的性质入手，找找易于实现的写法。注意到我们最多移动3个数字的位置，最终两个最低位的数，可能还有一个非0数作为最高位，而根据交换的性质，可以发现先移动那个数对于最终的结果没有影响，按照题意我们要先移动那个作为最高位的数，那现在既然调换顺序没有影响，不如把那个数留到最后再交换。于是，这道题的做法就出来了：1）贪心模拟，确定最低两位2）贪心模拟，确定最高位3）检查最后两位是否合法。
#include <bits/stdc++.h>
typedef long long ll;
const int inf = 0x3f3f3f3f;
using namespace std;
int n;
char s[22],tmp[22];
int solve(char a, char b) {
int p=n-1, ans=0;
for(p;p>=0;--p)if(s[p]==b)break;
if(p==-1)return inf;
for(int i=p+1;i<n;++i)swap(s[i],s[i-1]),++ans;
p=n-2;
for(p;p>=0;--p)if(s[p]==a)break;
if(p==-1)return inf;
for(int i=p+1;i<n-1;++i)swap(s[i],s[i-1]),++ans;
for(p=0;p<n;++p)if(s[p]!='0')break;
for(;p>=1;--p)swap(s[p],s[p-1]),++ans;
if(s[n-2]==a&&s[n-1]==b) return ans;
return inf;
}
int main() {
scanf(" %s",s);
memcpy(tmp,s,sizeof(s));
n=strlen(s);
int ans = inf;
ans = min(ans,solve('7','5'));
memcpy(s,tmp,sizeof(tmp));
ans = min(ans,solve('2','5'));
memcpy(s,tmp,sizeof(tmp));
ans = min(ans,solve('5','0'));
memcpy(s,tmp,sizeof(tmp));
ans = min(ans,solve('0','0'));
printf("%d
",(ans==inf)?-1:ans);
return 0;
}
F. Rain and Umbrellas
dp[i]表示到位置i的最小疲劳度。下面考虑转移，如果[i-1,i]不下雨dp[i]=dp[i-1]，即把所有伞扔掉走过来最小；如果[i-1,i]下雨怎么办呢？首先，不可能出现同时拿两把伞的情况，因为一定不会比同时拿一把优，那就只需要枚举上一把伞是哪一把就行了，dp[i] = min(dp[j]+(i-j)*w[j]) (j<i)。注意：一个位置可能有多把伞。
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
typedef long long ll;
const ll inf = 1e9+7;
const int N = 2000 + 50;
using namespace std;
int min(int a,int b){
if(a==-1)return b;
if(b==-1)return a;
if(a<b)return a;
return b;
}
int a, n, m, rn[N];
ll dp[N], w[N];
int main() {
scanf("%d%d%d",&a,&n,&m);
rep(i,0,a) w[i]=-1;
rep(i,1,n) {int l, r;
scanf("%d%d",&l,&r);
rep(j,l+1,r) rn[j] = 1;
}
rep(i,1,m) {int x, p;
scanf("%d%d",&x,&p);
w[x]=min(w[x],p);
}
dp[0]=0;
rep(i,1,a){
dp[i]=inf;
if(!rn[i]){
dp[i] = dp[i-1];
}
else {
rep(j,0,i-1) if(w[j]!=-1) {
dp[i] = min(dp[i], dp[j]+1LL*(i-j)*w[j]);
}
}
if(dp[i]==inf) return puts("-1"),0;
}
cout << dp[a] <<'
';
return 0;
}