社区讨论
不知道为啥我的解法除了样例全WA了
P5839[USACO19DEC] Moortal Cowmbat G参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m3cicd4a
- 此快照首次捕获于
- 2024/11/11 12:12 去年
- 此快照最后确认于
- 2025/11/04 14:55 4 个月前
状态： 设 为修改从第一个字符到第 个字符，并且最后一个字符为 的最小天数。
转移：
f(i-1,c) + a_{s_ic},
\min_{1\leq d\leq M} \left\{ f(i-K,d) + \sum_{j=i-k+1}^i a_{s_j c} \right\}
\right\}$$
**初值：** 对任意 $1\leq i < K, 1\leq c\leq M$,
$$f(0,c) = 0,\quad
f(i,c) = f(i-1,c) + a_{s_ic}$$
**目标：** $min_{1\leq c\leq M} f(n,c)$
注意到可以令
$$P(i,c) = \sum_{j=1}^i a_{s_j c},$$
则转移方程变为
$$f(i,c) = \min \left\{
f(i-1,c) + a_{s_ic},
\min_{1\leq d\leq M} \left\{ f(i-K,d) + P(i,c) - P(i-k,c) \right\}
\right\}$$
不知道为何这个解法除了样例全挂
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e5+5,MAXM=30;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll n,m,k;
char s[MAXN];
ll a[MAXM][MAXM];
ll p[MAXN][MAXM],f[MAXN][MAXM];
int main(){
ll i,j;
freopen("cowmbat.in","r",stdin);
freopen("cowmbat.out","w",stdout);
cin>>n>>m>>k;
for(i=1;i<=n;i++)
cin>>s[i];
#ifdef DEBUG
for(i=1;i<=n;i++)
cout<<"s["<<i<<"] = "<<s[i]<<' ';
cout<<endl;
#endif
for(i=0;i<m;i++)
for(j=0;j<m;j++)
cin>>a[i][j];
for(ll k=0;k<m;k++)
for(i=0;i<m;i++)
for(j=0;j<m;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
for(i=0;i<m;i++){
for(j=1;j<=n;j++){
p[j][i]=p[j-1][i]+a[s[j]-'a'][i];
}
}
#ifdef DEBUG
cout<<"p = \n";
for(i=1;i<=n;i++,cout<<endl)
for(j=0;j<m;j++)
cout<<p[i][j]<<' ';
#endif
for(i=0;i<m;i++){
f[0][i]=0;
for(j=1;j<k;j++)
f[j][i]=f[j-1][i]+a[s[j]-'a'][i];
}
for(i=k;i<=n;i++){
for(j=0;j<m;j++){
f[i][j]=f[i-1][j]+a[s[i]-'a'][j];
for(ll d=0;d<m;d++)
f[i][j]=min(f[i][j],f[i-k][d]+p[i][j]-p[i-k][j]);
}
}
#ifdef DEBUG
for(i=0;i<=n;i++,cout<<endl)
for(j=0;j<m;j++)
cout<<f[i][j]<<' ';
#endif
ll ans=INF;
for(i=0;i<m;i++)
ans=min(ans,f[n][i]);
cout<<ans<<endl;
return 0;
}
```回复
共 0 条回复，欢迎继续交流。
正在加载回复...