AtCoder Beginner Contest 288(D,E,F)
D(思维)
有一个数组，然后有\(q\)次询问，每一次输入一对\(l,r\),我们要判断这一段里面的数是不是好数组
好数组，在进行下面任意次操作后可以把这一段数字都变成\(0\),那么这就是个好数组
操作是选择一个\(i\)和一个\(c\),但是\(i+k-1\)要小于\(r\),我们会把\(i\)到\(i+k-1\)的数都加上\(c\)
这个正解感觉比较难想
我们把那些位置取模一样的加在一起，然后我们判断\(l,r\)这一段\(k\)个取模的结果的和都是一样的，那么就可以成为好数组，反之不然
这个可以这么来理解，可以假如只有一个长度为\(k\)的数组，我们只有这\(k\)个数都是一样的才可以，正好每一个位置都代表着不同的取模，就和上面的解法没有相悖的
至于证明，可以看这 博客
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=2e5+10;
const int mod=998244353;
int n,k;
int q;
int sum[maxn][14];
int a[maxn];
bool solve()
{
int l,r;
cin>>l>>r;
int p=sum[r][0]-sum[l-1][0];
for (int i=1;i<k;i++)
{
if(sum[r][i]-sum[l-1][i]!=p) return false;
}
return true;
}
signed main ()
{
cin>>n>>k;
for (int i=1;i<=n;i++)
{
cin>>a[i];
for (int j=0;j<k;j++)
{
sum[i][j]=sum[i-1][j];
}
sum[i][i%k]+=a[i];
}
cin>>q;
while (q--)
{
if(solve())
{
cout<<"Yes\n";
}
else
{
cout<<"No\n";
}
}
system ("pause");
return 0;
}
E(dp)
大意为一共有\(n\)个物品，每一个物品都有一个原来的价格，我们需要\(m\)个物品，而且，我们每次选择购买那一件物品还需要额外的费用，如果这个物品的编号在剩余还未售出的物品编号中排名为\(k\)，那么购买这一件物品的价值为原价加上\(c_k\)
问我们至少得到我们所需的\(m\)件物品的最少费用为多少
最开始想过是贪心，我找到最小的额外费用，然后把那些可以使用这个额外费用的加上去，但是可能我们还得加上那些不需要的，后来想了，不对，极端的想，万一，我所需要的还没有选择，但是因为每次先考虑较低的额外费用导致其他非必须的都购买了，显然不太可行
上面只是我的拙见
下面的解法是\(dp\)
\(dp[i] [j]\)代表从\(1\)到\(i\),我已经购买了\(j\)个物品
如果我还想要再购买一个物品的话，假设额外费用为\(add\),那么状态转移方程如下
\[dp[i][j+1]=dp[i-1][j]+val[i]+add \]然后我们来分析\(add\)
如果只是我们购买\(i\)是在前面已经购买了\(j\)的情况下，那么在\(1\)到\(i\)剩下就只有\(i-j\)个了，而\(i\)一定是比前面的都大的，所以我们这次的额外费用为\(c_{i-j}\)了
这是我们购买\(i\)在就是在第\(j+1\)次购买，但是如果我们购买\(i\)在第\(j+1\)次购买之前，对比第\(j+1\)次购买的排名一定是更大的，那么我们可以知道\(i\)物品可能存在的额外费用所有比他坐标小于等于的\(c\)，但是那些什么时候可以取，最小的\(c\)的坐标取决于目前的\(j+1\),即它作为最新的一次购买
所以我们又可以得到一个状态转移方程
\[dp[i][j+1]=dp[i-1][j]+val[i]+min(add,c[i-j]) \]#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=2e5+10;
const int mod=998244353;
int n,m;
int val[maxn],add[maxn];
bool must[maxn];
signed main ()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
cin>>val[i];
must[i]=false;
}
for (int i=1;i<=n;i++)
{
cin>>add[i];
}
for (int i=1;i<=m;i++)
{
int x;
cin>>x;
must[x]=true;
}
vector<int>dp(n+5,inf);
dp[0]=0;
for (int i=1;i<=n;i++)
{
vector<int>tmp(n+5,inf);
int w=inf;
for (int j=0;j<i;j++)
{
w=min(w,add[i-j]);
tmp[j+1]=min(tmp[j+1],dp[j]+val[i]+w);
if(!must[i])
{
tmp[j]=min(tmp[j],dp[j]);
}
}
dp=tmp;
}
int ans=*min_element(dp.begin(),dp.end());
cout<<ans<<"\n";
system ("pause");
return 0;
}
F(dp)
把一个字符串拆成若干个数，如可以把\(234\)拆成\(34\)和\(5\)这种，我们求的是把这个字符串拆成任可能的大小的数字的乘积
感觉做动态规划的题需要一步一步来
我们先什么都不考虑的话，就是直接暴力的求答案话，可以得到一个状态转移方程
\(f[i]\)是长度为\(i\)的字符串被拆后的乘积
\(dp[i]\)是前\(i\)个不同的拆分的乘积和
\(sum[i]\)是\(f[i]\)的前缀和
\(s[l] [r]\)是从\(l\)到\(r\)这一段形成的数字
\[dp[i]=\sum_{j=0}^{i-1}f[j]\times s[j+1][i] \]但是我们不太可能去一一枚举\(j\)的，那么我们可以对\(dp\)进行前缀处理，但是\(s[j+1] [i]\)这个还是要一一枚举呀
然后我们可以试着变换一下，
\[dp[i+1]=\sum_{j=0}^{i}f[j] \times s[j+1][i+1] \]再变化
\[dp[i+1]=\sum_{j=0}^{i}f[j] \times (s[j+1][i]\times10+s[i+1]) \]发现只有一点不同，那就是累加的最右端，但是我们仔细想一下，在\(i\)的时候，不会出现那样的情况，那么它的贡献是不计的，那么我们也可以忽略。
所以可以再把括号去掉
\[dp[i+1]=10\times\sum_{j=0}^{i}f[j] \times s[j+1][i]+\sum_{j=0}^{i}f[j] \times s[i+1] \]我们可以发现关系
\[dp[i+1]=10\times dp[i]+sum[i]\times s[i+1] \]其实也可以理解为把前面所有的情况都往前挪一位，就一个个位给\(s[i]\)
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=2e5+10;
const int mod=998244353;
int n;
string s;
int dp[maxn];
int sum[maxn];
signed main ()
{
cin>>n;
cin>>s;
s=" "+s;
dp[0]=0;
sum[0]=1;
for (int i=1;i<=n;i++)
{
int now=s[i]-'0';
dp[i]=(dp[i-1]*10+sum[i-1]*now)%mod;
sum[i]=(sum[i-1]+dp[i])%mod;
}
int ans=dp[n];
cout<<ans<<"\n";
system ("pause");
return 0;
}