链接：https://codeforces.com/contest/467/problem/C
这道题是求拿k个子序列且不能相交，问如何拿使得这些序列的值的和最大,那么阶段划分就很明显了，相当于这道问题对应的隐式DAG上一共可以被分成K层，接着就是枚举在哪个点转移，也就是是否取当前的往左m的区间，对应的就是在DAG求最短最长路的时候，是从同一层转移过来还是从前一层转移过来，取最大最小值贪心，类似dijk的思路。
#include<bits/stdc++.h>
using namespace std;
void check_max (int &a,int b) {a=max (a,b);}
typedef long long ll;
const int maxn=5100;
ll a[maxn];
ll dp[maxn][maxn];
ll pre[maxn];
int main () {
int n,m,k;
scanf ("%d%d%d",&n,&m,&k);
ll st=0;
for (int i=1;i<=n;i++) {
scanf ("%lld",&a[i]);
st+=a[i];
pre[i]=st;
}
memset (dp,0,sizeof (dp));
// for (int j=m;j<=n;j++)
// for (int i=1;i<=k;i++) {
// dp[i][j]=max (dp[i][j-1],dp[i-1][j-m]+pre[j]-pre[j-m]);
// }
for (int i=1;i<=k;i++)
for (int j=m;j<=n;j++) {
dp[i][j]=max (dp[i][j-1],dp[i-1][j-m]+pre[j]-pre[j-m]);
}
printf ("%lld
",dp[k][n]);
return 0;
}
链接：http://codeforces.com/problemset/problem/835/C
由题意可知每个星星在询问的时候的亮度是可知的，如果每个星星的初始亮度一样，那么这个题目就是一个裸的二维前缀和，但是现在因为每个星星的亮度不一样，我们可以考虑把一样的堆在一起处理。然后搞一个二维前缀和就可以了。其实二维前缀和就是一维的基础上面dp+容斥一下就可以了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+10;
const int N=110;
int num[11][maxn][maxn];
int t,r1,c1,r2,c2;
int n,m,q,x;
ll ans=0;
int main () {
while (~scanf ("%d%d%d",&n,&q,&m)) {
memset (num,0,sizeof (num));
for (int i=1,x,y,s;i<=n;i++) {
scanf ("%d%d%d",&x,&y,&s);
num[s][x][y]++;
}
// for (int i=0;i<=m;i++)
// for (int j=1;j<=N;j++)
// for (int k=1;k<=N;k++) {
// num[i][j][k]+=num[i][j][k-1];
// }
// for (int i=0;i<=m;i++)
// for (int j=1;j<=N;j++)
// for (int k=1;k<=N;k++) num[i][j][k]+=num[i][j-1][k];
for (int i=0;i<=m;i++)
for (int j=1;j<=N;j++)
for (int k=1;k<=N;k++) {
num[i][j][k]+=num[i][j-1][k]+num[i][j][k-1]-num[i][j-1][k-1];
}
while (q--) {
scanf ("%d%d%d%d%d",&t,&r1,&c1,&r2,&c2);
ans=0;
for (int i=0;i<=m;i++) {
x=num[i][r2][c2]-num[i][r1-1][c2]-num[i][r2][c1-1]+num[i][r1-1][c1-1];
ll now=((i+t)%(m+1))*x;
ans+=now;
}
printf ("%lld
",ans);
}
}
return 0;
}
链接：http://codeforces.com/problemset/problem/706/C
这道题的状态划分也非常的明显，并且我们很容易想到每层图都分别有两个点来表示到达这层时候，当前字符串是反转还是不反转，那么接着我们就可以枚举状态转移了，很容易就知道这个dp只能从上一个状态枚举过来，也就是同层图直接不存在连边，条件是我的字符串要比前一个状态的字符字典序要小。因为只有层之间的枚举，所以一重循环就够了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void check_max (ll &a,ll b) {a=max (a,b);}
void check_min (ll &a,ll b) {a=min (a,b);}
const int maxn=1e5+10;
const ll inf=1e15;
ll a[maxn];
vector <string> v (maxn);
ll dp[maxn][2];
int main () {
ios::sync_with_stdio (false);
int n;
cin>>n;
ll ans=inf;
for (int i=1;i<=n;i++) cin>>a[i];
v.assign (n+1,"");
for (int i=1;i<=n;i++) cin>>v[i];
for (int i=1;i<=n;i++) dp[i][0]=dp[i][1]=inf;
dp[1][0]=0,dp[1][1]=a[1];
for (int i=2;i<=n;i++) {
string s1=v[i],s2=v[i-1];
string __s1=s1,__s2=s2;
reverse (__s1.begin (),__s1.end ());
reverse (__s2.begin (),__s2.end ());
if (s1>=s2) check_min (dp[i][0],dp[i-1][0]);
if (s1>=__s2) check_min (dp[i][0],dp[i-1][1]);
if (__s1>=s2) check_min (dp[i][1],dp[i-1][0]+a[i]);
if (__s1>=__s2) check_min (dp[i][1],dp[i-1][1]+a[i]);
}
ans=min (dp[n][0],dp[n][1]);
if (ans==inf) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
链接：http://codeforces.com/problemset/problem/611/C
和上面某题一样，也是分开处理横着放或者是竖着放的状况，分别搞一个前缀和，然后直接求部分和就可以。不过这题要处理一下边界，就是横着放和竖着放在最后容斥的时候需要微调一下下标。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void check_max (ll &a,ll b) {a=max (a,b);}
void check_min (ll &a,ll b) {a=min (a,b);}
const int maxn=510;
char s[maxn][maxn];
ll sumc[maxn][maxn],sumr[maxn][maxn];
const ll mod=1e9+7;
int main () {
int n,m;
scanf ("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf ("%s",s[i]+1);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) {
sumr[i][j]=sumr[i-1][j]+sumr[i][j-1]-sumr[i-1][j-1];
sumc[i][j]=sumc[i-1][j]+sumc[i][j-1]-sumc[i-1][j-1];
if (s[i][j]=='.') {
if (s[i-1][j]=='.') sumr[i][j]++;
if (s[i][j-1]=='.') sumc[i][j]++;
}
}
int q; scanf ("%d",&q);
while (q--) {
int r1,c1,r2,c2;
scanf ("%d%d%d%d",&r1,&c1,&r2,&c2);
ll ans=0;
ans+=sumr[r2][c2]-sumr[r1][c2]-sumr[r2][c1-1]+sumr[r1][c1-1];
ans+=sumc[r2][c2]-sumc[r1-1][c2]-sumc[r2][c1]+sumc[r1-1][c1];
printf ("%lld
",ans);
}
return 0;
}
链接：https://codeforces.com/contest/711/problem/C
好题好题，夸爆。是这样的，这道题目的状态我们可以很明显的从题目里面挖掘出字眼，就是k组。那么我们把k当作是隐式图里面的层数，那么接下来我们考虑什么，是否可以同层之间转换，我们这道题的dp转移的第一层循环必然是2-n这很明显吧，因为要一棵树一棵树推过去。那么随着i的推进，我们的层数该如何改变呢，是不是取决于当前树要染的颜色和前一棵树的颜色，然而这些都可能是未知量 （在当前树没有染色的情况下），所以我们枚举一下前一棵树和当前树的状态，如果不同，那么它就是从前一层图的节点里面过来的，不然就是同一层的，也就是k不发生改变。注意当这棵树已经被染色的情况下，我只需要一重循环枚举前一棵树的颜色即可。那么题目就豁然开朗了。下面给出dp的式子：
(1.dp[i][a[i]][k]=min (dp[i-1][a[i]][k],dp[i][a[i]][k]) 2.dp[i][a[i]][k]=min (dp[i][a[i]][k],dp[i-1][j][k-1]))
(3.dp[i][j][k]=min (dp[i-1][j][k]+cost,dp[i][j][k]) 4.dp[i][j][k]=min (dp[i-1][h][k-1]+cost,dp[i][j][k]))
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=102;
const ll inf=1e15;
void check_min (ll &a,ll b) {a=min (a,b);}
ll a[maxn],cost[maxn][maxn],dp[maxn][maxn][maxn];
ll n,m,p;
int main () {
while (~scanf ("%lld%lld%lld",&n,&m,&p)) {
for (int i=1;i<=n;i++) scanf ("%lld",&a[i]);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) scanf ("%lld",&cost[i][j]);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
for (int k=1;k<=p;k++) dp[i][j][k]=inf;
if (a[1]==0) for (int j=1;j<=m;j++) dp[1][j][1]=cost[1][j];
else dp[1][a[1]][1]=0;
for (int i=2;i<=n;i++) {
if (a[i]) {
for (int j=1;j<=m;j++)
for (int k=1;k<=p;k++) {
if (j==a[i]) check_min (dp[i][a[i]][k],dp[i-1][j][k]);
else check_min (dp[i][a[i]][k+1],dp[i-1][j][k]);
}
}
else {
for (int j=1;j<=m;j++)
for (int k=1;k<=m;k++)
for (int h=1;h<=p;h++) {
if (j==k) check_min (dp[i][j][h],dp[i-1][k][h]+cost[i][j]);
else check_min (dp[i][j][h+1],dp[i-1][k][h]+cost[i][j]);
}
}
}
ll ans=inf;
for (int j=1;j<=m;j++) check_min (ans,dp[n][j][p]);
if (ans!=inf) printf ("%lld
",ans);
else printf ("-1
");
}
return 0;
}
链接：https://codeforces.ml/contest/567/problem/C
刚上去就在嗯想dp，想得超级复杂，结果最后其实挺傻逼的。这道题教了一个道理，一个题不能直接上去就非要什么做法直接上面怼，要先观察题目条件和限制，看下朴素的解法或者说暴力解法容不容易想到，然后再去进一步考虑dp关系。这道题我们发现只需要统计每一个数前面符合条件的和后面符合条件数目的乘积求和就行了，因为这道题是三项等比，所以我们直接嗯dp或者乱搞也可以，关键是思路要清晰。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void check_min (ll &a,ll b) {a=min (a,b);}
void check_max (ll &a,ll b) {a=max (a,b);}
const int maxn=2e5+10;
ll dp[maxn],dp2[maxn];
map <ll,int> mp;
ll a[maxn];
int main () {
int n,k;
scanf ("%d %d",&n,&k);
mp.clear ();
for (int i=1;i<=n;i++) {
scanf ("%lld",&a[i]);
if (a[i]%k==0) dp[i]=mp[a[i]/k];
mp[a[i]]++;
}
mp.clear ();
for (int i=n;i>=1;i--) {
dp2[i]=mp[a[i]*k];
mp[a[i]]++;
}
ll ans=0;
for (int i=1;i<=n;i++) ans+=dp[i]*dp2[i];
printf ("%lld
",ans);
return 0;
}