T1

大意是给定两个数字串 $A$ 和 $B$

对 $A$ 可以进行这三种操作

1.将第$i$位替换成$j$ 代价为 $min(|i-j|,10-|i-j|)$

2.删除第 $i$ 位,代价为 $A_i$

3.插入一个数 $k$ 代价为 $k$ ,并且以后不能修改或者删除

问至少要多少代价才能将 $A$ 变成 $B$

我严格地打表 证明了 1 操作最优的是对每个位置进行一次,然后2 3等价,因此设$f[i][j]$ 表示 $A_i $ 和 $B_j$ 之前的已经匹配的代价的最小值

那么状态转移方程就是

$f[i][j]=\min\limits_{k=1}^{j-1}(f[i-1][k]-s[k]+s[j-1])+cost(i,j)$

这是一个 $O(n^3)$ 的dp,然后我们考虑维护 $f[i-1][k]-s[k]$ 的最小值,好像直接每次比较最小值也可以,我用了一个优先队列来做,复杂度没有问题,但是代码只有40分

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=2020;

char s1[maxn],s2[maxn];
int f[maxn][maxn];
int s[maxn];
int n,m;
int a[maxn],b[maxn];
int tmp[maxn];

int ldis(int a,int b)
{
return min(abs(a-b),10-abs(a-b));
}

priority_queue <int> q;

signed main()
{
register int i,j,k;
scanf("%s",s1+1);
scanf("%s",s2+1);
n=strlen(s1+1);
m=strlen(s2+1);
if(n>m)
{
swap(n,m);
swap(s1,s2);
}
for(i=1;i<=n;i++) a[i]=s1[i]-'0';
for(i=1;i<=m;i++) b[i]=s2[i]-'0',s[i]=s[i-1]+b[i];
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(i=1;i<=n;i++)
{
while(!q.empty()) q.pop();
memset(tmp,0x3f,sizeof(tmp));
q.push(-(f[i-1][0]-s[0]));
for(j=1;j<=m;j++)
{
f[i][j]=-q.top()+s[j-1]+ldis(a[i],b[j]);
q.push(-(f[i-1][j]-s[j]));
}
}
printf("%lld",f[n][m]);
return 0;
}

T2

每个物品上面只能放 $b_i$ 个物品,放完后获得 $a_i$ 奖励,问你奖励的最大值。

这个我发现是一个单调不下降单调子序列,但是我的决策出了一点问题,然后挂了

实际上对每个数我们把它放在一个优先队列里面,为了保证每一个的 $b[i]$ 都大于等于 $b[now]$ 我们现在对每个元素按照 $b$ 排序

然后当我们可以决策的时候(能再放一本书,此时答案加最大值即可)

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=1010000;
const int modp=910666;

int f[maxn],n,tmp[maxn];
int ans=0;

priority_queue < int > q;

struct bk{
int a,b;
bool operator <(const bk &bb)
const {
if(b==bb.b) return a<bb.a;
return b<bb.b;
}
}a[maxn];

signed main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n;
for(i=1;i<=n;i++) cin>>a[i].a;
for(i=1;i<=n;i++) cin>>a[i].b;
sort(a+1,a+n+1);
//int target=a[n].b;
//int sz=0;
//a[0].b=-1;
// for(i=1;i<=n;i++)
// {
// if(a[i].b!=a[i-1].b)
// {
// sz+=a[i].b-a[i-1].b-1;
// f[a[i].b]+=f[a[i-1].b]+a[i].a;
// }
// else q.push(a[i].a);
// }
a[n+1].b=a[n].b+1;
for(i=n;i;i--)
{
q.push(a[i].a);
f[a[i].b]=f[a[i+1].b];
if(a[i].b!=a[i+1].b)
{
//f[a[i].b]+=f[a[i+1].b]+a[i].a;
int delta=a[i+1].b-a[i].b;
for(j=1;!q.empty()&&j<=delta;j++)
{
f[a[i].b]+=q.top();
q.pop();
}
f[a[i].b]%=modp;
}

}
ans=f[a[1].b];
for(i=1;!q.empty()&&i<=a[1].b;i++) ans+=q.top(),q.pop();
cout<<(1ll*ans%modp)<<endl;
return 0;
}

然而上面的两个代码都挂了,餐毙了