codeforces的dp专题
1.(467C)http://codeforces.com/problemset/problem/467/C
题意：有一个长为n的序列，选取k个长度为m的子序列（子序列中不能有位置重复），求所取的k个序列求和的最大值是多少
分析：设dp[i][j]在[j,n]范围内取了i个子序列求和所得的最大值，用sum[i]表示[1,i]的求和。转移方程为dp[i][j]=max(dp[i-1][j+m]+sum[j+m-1]-sum[j-1],dp[i][j+1])，表示要不要选择[j,j+m-1]这段为其中一个子序列
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn=;
ll dp[maxn][maxn],a[maxn],sum[maxn]; int main()
{
ll n,m,k,i,j,x,y,z,ans;
while ( scanf("%lld%lld%lld",&n,&m,&k)!=EOF ) {
for ( i=;i<=n;i++ ) scanf("%lld",&a[i]);
sum[]=;
for ( i=;i<=n;i++ ) sum[i]=sum[i-]+a[i];
memset(dp,,sizeof(dp));
ans=;
for ( i=;i<=k;i++ ) {
dp[i][n-i*m+]=sum[n]-sum[n-i*m];
for ( j=n-i*m;j>;j-- ) {
dp[i][j]=max(dp[i-][j+m]+sum[j+m-]-sum[j-],dp[i][j+]);
}
}
for ( i=;i<=n-k*m+;i++ ) ans=max(ans,dp[k][i]);
printf("%lld\n",ans);
}
return ;
}
467C
2.（706C）http://codeforces.com/problemset/problem/706/C
题意：有n个字符串，每个字符串反转需要a[i]的费用，先求花费最少使得对于任意第i个字符串的字典序都大于等于第i-1个字符串,若不存在输出-1
分析：设dp[i][j]，j=0表示第i个字符串不反转，j=1表示第i个字符串反转，dp[i][j]表示前i个字符串都已经按顺序排好的最小花费（初始化除第一项外都为inf）。
转移方程有4条：
if ( s[i]>=s[i-1] ) dp[i][0]=min(dp[i][0],dp[i-1][0]);
if ( s[i]>=s_[i-1] ) dp[i][0]=min(dp[i][0],dp[i-1][1]);
if ( s_[i]>=s[i-1] ) dp[i][1]=min(dp[i][1],dp[i-1][0]+a[i]);
if ( s_[i]>=s_[i-1] ) dp[i][1]=min(dp[i][1],dp[i-1][1]+a[i]);
注意：审题！操作是整体反转，字典序的顺序是大于等于（不要遗漏等于）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
const ll maxn=1e5+;
const ll inf=1e15;
ll dp[maxn][],a[maxn];
string s[maxn],s_[maxn]; int main()
{
ll n,m,i,j,k,x,y,z,ans;
while ( scanf("%lld",&n)!=EOF ) {
for ( i=;i<=n;i++ ) scanf("%d",&a[i]);
for ( i=;i<=n;i++ ) {
cin>>s[i];
s_[i]=s[i];
reverse(s_[i].begin(),s_[i].end());
}
//for ( i=1;i<=n;i++ ) cout<<s[i]<<" "<<s_[i]<<endl;
for ( i=;i<=n;i++ ) dp[i][]=dp[i][]=inf;
dp[][]=;
dp[][]=a[];
for ( i=;i<=n;i++ ) {
if ( s[i]>=s[i-] ) dp[i][]=min(dp[i][],dp[i-][]);
if ( s[i]>=s_[i-] ) dp[i][]=min(dp[i][],dp[i-][]);
if ( s_[i]>=s[i-] ) dp[i][]=min(dp[i][],dp[i-][]+a[i]);
if ( s_[i]>=s_[i-] ) dp[i][]=min(dp[i][],dp[i-][]+a[i]);
}
ans=min(dp[n][],dp[n][]);
if ( ans==inf ) printf("-1\n");
else printf("%lld\n",ans);
}
return ;
}
706C
3.（611C）http://codeforces.com/problemset/problem/611/C
题意：有一个n*m的地图，地图上有“.”和“#”，当相邻的两块都为“.”时可以放置一个多米诺骨牌，现给定一个矩形区域，问在这个矩形区域内有多少种放置骨牌的方法
分析：因为有横着放和竖着放两种方式，所以我们将这两种方式分开来看。用row[i][j]表示对于第i行前j个方格多米诺骨牌横放有多少种可能。col[j][i]表示对于第j列前i个方格多米诺骨牌竖着放有多少可能。
最后对于左上角为(x1,y1)和右下角为(x2,y2)大小的矩阵来说，该方格中的方案数为：
for ( i=x1;i<=x2;i++ ) ans+=(row[i][y2]-row[i][y1]);
for ( i=y1;i<=y2;i++ ) ans+=(col[i][x2]-col[i][x1]);
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn=;
char s[maxn][maxn];
ll mp[maxn][maxn],row[maxn][maxn],col[maxn][maxn]; int main()
{
ll n,m,i,j,k,x,y,z,x1,x2,y1,y2,ans,q;
while ( scanf("%lld%lld",&n,&m)!=EOF ) {
for ( i=;i<=n;i++ ) scanf("%s",s[i]+);
memset(mp,,sizeof(mp));
memset(row,,sizeof(row));
memset(col,,sizeof(col));
for ( i=;i<=n;i++ ) {
for ( j=;j<=m;j++ ) {
if ( s[i][j]=='.' ) mp[i][j]=;
}
}
for ( i=;i<=n;i++ ) {
for ( j=;j<=m;j++ ) {
row[i][j]=row[i][j-];
if ( mp[i][j] && mp[i][j-] ) row[i][j]++;
}
}
for ( j=;j<=m;j++ ) {
for ( i=;i<=n;i++ ) {
col[j][i]=col[j][i-];
if ( mp[i][j] && mp[i-][j] ) col[j][i]++;
}
}
scanf("%lld",&q);
while ( q-- ) {
scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
ans=;
for ( i=x1;i<=x2;i++ ) ans+=(row[i][y2]-row[i][y1]);
for ( i=y1;i<=y2;i++ ) ans+=(col[i][x2]-col[i][x1]);
printf("%lld\n",ans);
}
}
return ;
}
611C
4.（835C）http://codeforces.com/problemset/problem/835/C
题意：有一个最大范围为100*100的方格，规定星星最大的亮度为m,现有n个星星，每颗星星坐标为（x,y），初始亮度为s。现有q个询问，每个询问有t秒（时间）和一个矩形大小，矩形的左下角为 (x1,y1) 右上角为(x2,y2)。现求在这个矩形区域内的所有星星的亮度之和。对于每颗星星每过1s，亮度+1,当亮度为m+1时亮度变为0。
分析：对于一个矩形面积中的总亮度为这个矩形中的星星数量*他们各自的亮度求和。因为亮度的范围最大为10，所以我们考虑将不同的初始亮度的星星存入不同的数组中，每个亮度的用一个二维数组维护数量。对于每次访问的矩形范围，每个亮度都扫一次再相加
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn=;
const ll maxk=;
const ll N=;
ll num[maxk][maxn][maxn]; int main()
{
ll n,q,m,i,j,k,x,y,z,ans,cnt,s,t,x1,x2,y1,y2,now;
while ( scanf("%lld%lld%lld",&n,&q,&m)!=EOF ) {
memset(num,,sizeof(num));
for ( i=;i<=n;i++ ) {
scanf("%lld%lld%lld",&x,&y,&s);
num[s][x][y]++;
}
for ( i=;i<=m;i++ ) {
for ( j=;j<=N;j++ ) {
for ( k=;k<=N;k++ ) num[i][j][k]+=num[i][j][k-];
}
}
for ( i=;i<=m;i++ ) {
for ( j=;j<=N;j++ ) {
for ( k=;k<=N;k++ ) num[i][j][k]+=num[i][j-][k];
}
}
while ( q-- ) {
scanf("%lld%lld%lld%lld%lld",&t,&x1,&y1,&x2,&y2);
ans=;
for ( i=;i<=m;i++ ) {
x=num[i][x2][y2]-num[i][x1-][y2]-num[i][x2][y1-]+num[i][x1-][y1-];
now=((i+t)%(m+))*x;
ans+=now;
}
printf("%lld\n",ans);
}
}
return ;
}
835C
5.（711C）http://codeforces.com/problemset/problem/711/C
题意：有n颗树，初始时每棵树可能没有颜色(c[i]==0)，可能已经有颜色了(c[i]!=0),先要从m（[1,m]）种颜色中给那些未上色的树上色，若要给第i颗树上第j个颜色，则需要花费cost[i][j]的颜料。现在要使从左到右的n颗树分成k组（一组的定义是连续的树具有相同的颜色算作一组），现要求恰好分成k组需要的颜料的最小值
分析：设dp[i][j][k]表示前i颗树已经分成k组，第i颗树的颜色是j的情况花费的最小费用。将数组初始化为inf。
当a[i]确定时 dp[i][a[i]][k]=max(dp[i][a[i]][k],dp[i-1][j][k-1]) (j!=a[i])
dp[i][a[i]][k]=max(dp[i][a[i]][k],dp[i-1][j][k]) (j==a[i])
当a[i]不确定时 dp[i][j][k]=max(dp[i][j][k],dp[i-1][h][k-1])+cost[i][j] (h!=j)
dp[i][j][k]=max(dp[i][j][k],dp[i-1][h][k])+cost[i][j] (h==j)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn=;
const ll inf=1e15;
ll a[maxn],dp[maxn][maxn][maxn],cost[maxn][maxn]; int main()
{
ll n,m,p,i,j,k,h,x,y,z,ans;
while ( scanf("%lld%lld%lld",&n,&m,&p)!=EOF ) {
for ( i=;i<=n;i++ ) scanf("%lld",&a[i]);
for ( i=;i<=n;i++ ) {
for ( j=;j<=m;j++ ) scanf("%lld",&cost[i][j]);
}
for ( i=;i<=n;i++ ) {
for ( j=;j<=m;j++ ) {
for ( k=;k<=p;k++ ) dp[i][j][k]=inf;
}
}
if ( a[]== ) {
for ( j=;j<=m;j++ ) dp[][j][]=cost[][j];
}
else dp[][a[]][]=;
for ( i=;i<=n;i++ ) {
if ( a[i]!= ) {
for ( k=;k<=m;k++ ) {
for ( h=;h<=p;h++ ) {
if ( dp[i-][k][h]!=- ) {
if ( a[i]==k ) dp[i][a[i]][h]=min(dp[i][a[i]][h],dp[i-][k][h]);
else dp[i][a[i]][h+]=min(dp[i][a[i]][h+],dp[i-][k][h]);
}
}
}
}
else {
for ( j=;j<=m;j++ ) {
for ( k=;k<=m;k++ ) {
for ( h=;h<=p;h++ ) {
if ( dp[i-][k][h]!=- ) {
if ( j==k ) dp[i][j][h]=min(dp[i][j][h],dp[i-][k][h]+cost[i][j]);
else dp[i][j][h+]=min(dp[i][j][h+],dp[i-][k][h]+cost[i][j]);
}
}
}
}
}
}
ans=inf;
for ( j=;j<=m;j++ ) {
ans=min(dp[n][j][p],ans);
}
if ( ans!=inf ) printf("%lld\n",ans);
else printf("-1\n");
}
return ;
}
711C
6.（567C）http://codeforces.com/problemset/problem/567/C
题意：给你一个序列,求序列中长度为3的公比为m的子序列的个数。
分析：设置一个num数组记录某个数已经出现的个数，设置cnt数组,cnt[i]表示当i出现时,ans+=cnt[i]（即cnt[i]表示i作为等比数列的第三项时，当前有多少个子序列满足条件）。特别注意当m==1时需要特别判断。还有当序列中出现0时需要记录并且单独考虑
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll maxn=2e5+;
map<ll,ll>num,cnt; int main()
{
ll n,m,i,j,k,x,y,z,ans;
while ( scanf("%lld%lld",&n,&m)!=EOF ) {
num.clear();
cnt.clear();
if ( m== ) {
ans=;
set<int>s;
for ( i=;i<=n;i++ ) {
scanf("%lld",&x);
num[x]++;
s.insert(x);
}
set<int>::iterator it;
for ( it=s.begin();it!=s.end();it++ ) {
x=*it;
y=num[x];
ans+=y*(y-)*(y-)/;
}
printf("%lld\n",ans);
continue;
}
ans=;
z=;
for ( i=;i<=n;i++ ) {
scanf("%lld",&x);
num[x]++;
if ( x%m== && x!= ) {
cnt[x*m]+=num[x/m];
}
else if ( x== ) z++;
ans+=cnt[x];
}
ans+=z*(z-)*(z-)/;
printf("%lld\n",ans);
}
return ;
}
567C
7.(339C)http://codeforces.com/problemset/problem/339/C
题意：有不同质量的砝码无限多个，现在只让你在天平两边放入m个，要求
1.每次在天平放一个，一次左边，下一次右边
2.相邻两次质量必须不同
3.放入砝码后，保证放入的这边总重严格大于另外一边。
分析：DFS，将往天平的左右加砝码，转变成往一个地方加质量和减质量。DFS时记录sum,last,id，分别表示当前求值之和，上一个砝码是哪一个，这是第几次放砝码（决定是加质量还是减质量）
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
const int maxm=;
int path[maxn],d[maxm];
char s[maxm];
int cnt,m; bool f(int last,int sum,int id)
{
if ( id==m+ ) return true;
bool ok;
if ( id%== ) ok=true;
else ok=false;
int x,y,z;
for ( int i=;i<=cnt;i++ ) {
if ( d[i]==last ) continue;
if ( ok ) {
x=sum+d[i];
if ( x> ) {
if ( f(d[i],x,id+) ) {
path[id]=d[i];
return true;
}
}
}
else {
x=sum-d[i];
if ( x< ) {
if ( f(d[i],x,id+) ) {
path[id]=d[i];
return true;
}
}
}
}
return false;
} int main()
{
int i,j,k,x,y,z;
bool flag;
while ( scanf("%s",s+)!=EOF ) {
scanf("%d",&m);
cnt=;
for ( i=;i<=;i++ ) {
if ( s[i]=='' ) d[++cnt]=i;
}
flag=f(,,);
if ( flag ) {
printf("YES\n");
for ( i=;i<=m;i++ ) {
printf("%d",path[i]);
if ( i!=m ) printf(" ");
else printf("\n");
}
}
else printf("NO\n");
}
return ;
}
339C
8.（713C）http://codeforces.com/problemset/problem/713/C
题意：给定一个序列，可以进行若干次操作，每次操作选择一个数让它+1或-1，问最少要几次操作使得序列变为严格单调递增序列
分析：有两个性质：1.若为非严格递增序列，一定可以做到在最少的操作次数下使得改变后的序列中的元素是原序列的元素
2.若改为严格递增序列，则将每个数-i，再进行以上操作，就能保证改变后的是非严格递增，最后每个数+i则能保证严格递增
设dp[i][j]表示将原序列前i个数变成按递增顺序并且第i个数最大为j（离散后的j）的序列需要的最小花费，
有dp[i][j]=min(dp[i][j-1]+abs(a[i]-c[j])) i==1
=min(dp[i][j-1],dp[i-1][j]+abs(a[i]-c[j])) i!=1
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const ll maxn=;
const ll inf=1e15;
ll a[maxn],b[maxn],dp[maxn][maxn],c[maxn]; bool cmp1(int x,int y)
{
return x<y;
} bool cmp2(int x,int y)
{
return x>y;
} int main()
{
ll n,m,i,j,k,x,y,z,cnt,ans;
while ( scanf("%lld",&n)!=EOF ) {
for ( i=;i<=n;i++ ) {
scanf("%lld",&a[i]);
a[i]-=i;
b[i]=a[i];
}
sort(b+,b++n);
cnt=;
for ( i=;i<=n;i++ ) {
if ( i== ) c[++cnt]=b[i];
else {
if ( b[i]==b[i-] ) continue;
else c[++cnt]=b[i];
}
}
for ( i=;i<=n;i++ ) {
for ( j=;j<=cnt;j++ ) dp[i][j]=inf;
}
for ( j=;j<=cnt;j++ ) {
if ( a[]>=c[j] ) x=a[]-c[j];
else x=c[j]-a[];
dp[][j]=min(dp[][j-],x);
}
for ( i=;i<=n;i++ ) {
for ( j=;j<=cnt;j++ ) {
if ( a[i]>=c[j] ) x=a[i]-c[j];
else x=c[j]-a[i];
dp[i][j]=min(dp[i][j-],dp[i-][j]+x);
}
}
ans=dp[n][cnt];
printf("%lld\n",ans);
}
return ;
}
713C
9.（4D）http://codeforces.com/problemset/problem/4/D
题意：有n个信封，有一个信纸大小为w*h。现在让你从n个信封中取出一些信封，使其满足一些条件（后一个信封的大小（长/宽）都要大于前一个信封的大小（长/宽）；并且都需要比信纸的大小要大）。先求最多能取出多少信封。
分析：类似于求最长上升子序列。先将所有信封排序（长为第一关键字，宽为第二关键字进行排序），然后对于第i个信封来说，访问它前面所有的信封看是否满足条件，用类似于最长上升子序列的方式更新该信封的“最长长度”并且需要记录上一个信封的编号。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
struct node{
int w,h,id,pre,len;
bool ok;
}arr[maxn];
int d[maxn]; bool cmp(node a,node b)
{
if ( a.w==b.w ) return a.h<b.h;
return a.w<b.w;
} bool cmp1(node a,node b)
{
return a.id<b.id;
} int main()
{
int n,w,h,i,j,k,m,ans,x,y,z,cnt,num,len;
while ( scanf("%d%d%d",&n,&w,&h)!=EOF ) {
for ( i=;i<=n;i++ ) {
scanf("%d%d",&arr[i].w,&arr[i].h);
arr[i].id=i;
arr[i].pre=-;
arr[i].len=;
if ( arr[i].w>w && arr[i].h>h ) arr[i].ok=true;
else arr[i].ok=false;
}
sort(arr+,arr++n,cmp);
ans=;
cnt=-;
for ( i=;i<=n;i++ ) {
if ( !arr[i].ok ) continue;
for ( j=;j<i;j++ ) {
if ( !arr[j].ok ) continue;
if ( arr[i].w>arr[j].w && arr[i].h>arr[j].h ) {
len=arr[j].len+;
if ( len>arr[i].len ) {
arr[i].len=len;
arr[i].pre=j;
}
}
}
if ( arr[i].len>ans ) {
ans=arr[i].len;
cnt=i;
}
}
if ( cnt==- ) printf("0\n");
else {
m=;
while ( cnt!=- ) {
d[++m]=arr[cnt].id;;
cnt=arr[cnt].pre;
}
printf("%d\n",m);
for ( i=m;i>;i-- ) {
printf("%d",d[i]);
if ( i!= ) printf(" ");
else printf("\n");
}
}
}
return ;
}
4D
10.(761C)http://codeforces.com/problemset/problem/761/C
题意：有 n 个字符串，每个字符串的长度是m，如果认定一个字符串是一个密码，则必须满足：
1：至少有1个数字。2：至少有一个小写字母。3：至少有一个 #、*或&
现在有n个光标，每个光标指向这 n 个字符串。现在可以移动光标，最后使得所有光标指向的字符能组成一个密码。（字符串是循环的）
分析：费用流，设置超级源点s和超级汇点t,对于每个字符串设置一个点，对于要求的三类符号各设置一个点，计算每个字符串分别获得这三类符号所需要的最小费用，然后s到各个字符串建容量为1费用为0的边。对于每个字符串到三类字符的点，若费用不为Inf（初始值）,建容量为1，费用为每个字符串得到该类字符的最少花费的费用。最后将三类字符串的点和t建费用为0，容量为1的边。跑一遍最小费用流
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn=;
const int inf=1e9;
struct edge{
int from,to,flow,cost;
edge(int u,int v,int f,int c):from(u),to(v),flow(f),cost(c) {}
};
int n,s,t;
long long cost;
vector<edge>E;
vector<int>G[maxn];
bool vis[maxn];
int d[maxn],p[maxn],a[maxn];
char S[maxn][maxn];
int dp[maxn][]; void init()
{
for ( int i=;i<=n;i++ ) G[i].clear();
E.clear();
} void addedge(int u,int v,int f,int c)
{
E.push_back(edge(u,v,f,c));
E.push_back(edge(v,u,,-c));
int m=E.size();
G[u].push_back(m-);
G[v].push_back(m-);
} bool bellmanford(int& flow)
{
for ( int i=;i<=n;i++ ) d[i]=inf;
memset(vis,false,sizeof(vis));
d[s]=;
vis[s]=true;
p[s]=;
a[s]=inf;
queue<int>que;
que.push(s);
while ( !que.empty() ) {
int u=que.front();
que.pop();
vis[u]=false;
for ( int i=;i<G[u].size();i++ ) {
edge& e=E[G[u][i]];
if ( e.flow> && d[e.to]>d[u]+e.cost ) {
d[e.to]=d[u]+e.cost;
p[e.to]=G[u][i];
a[e.to]=min(a[u],e.flow);
if ( !vis[e.to] ) {
que.push(e.to);
vis[e.to]=true;
}
}
}
}
if ( d[t]==inf ) return false;
flow+=a[t];
cost+=(long long)d[t]*(long long)a[t];
for ( int u=t;u!=s;u=E[p[u]].from ) {
E[p[u]].flow-=a[t];
E[p[u]^].flow+=a[t];
}
return true;
} int mincost()
{
int flow=;
cost=;
while ( bellmanford(flow));
return flow;
} int main()
{
int N,M,i,j,k,ans,x;
char c;
while ( scanf("%d%d",&N,&M)!=EOF ) {
s=;
n=N+;
t=n;
init();
for ( i=;i<=N;i++ ) scanf("%s",S[i]+);
for ( i=;i<=N;i++ ) {
for ( j=;j<;j++ ) dp[i][j]=inf;
}
for ( i=;i<=N;i++ ) {
for ( j=;j<=M;j++ ) {
c=S[i][j];
x=min(j-,M+-j);
if ( c>='' && c<='' ) dp[i][]=min(dp[i][],x);
else if ( c>='a' && c<='z' ) dp[i][]=min(dp[i][],x);
else dp[i][]=min(dp[i][],x);
}
}
for ( i=;i<=N;i++ ) addedge(s,i,,);
for ( i=;i<=N;i++ ) {
for ( j=;j<;j++ ) {
if ( dp[i][j]!=inf ) addedge(i,j+N+,,dp[i][j]);
}
}
for ( i=;i<;i++ ) addedge(i++N,t,,);
mincost();
printf("%lld\n",cost);
}
return ;
}
761C
11.（269B）http://codeforces.com/problemset/problem/269/B
题意：给出一个实数轴，上面散布着n个点，总共有m种，每个点属于一种，问最少挪多少个点能将数轴上的点按各自的种类从小到大排序。
分析：从反面出发，考虑最多有多少个点可以保持不动，即求最长非严格递增子序列。设dp[i]表示从[1,i]包含第i个点的最长非严格递增子序列的最长长度。假设第i个点的种类为s[i]，dp[i]=max(dp[j])+1(s[i]>=s[j] && i>j),同时设置ans记录最长的非严格递增子序列的长度，最后的答案为n-ans
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
struct node{
int s;
double x;
}arr[maxn];
int dp[maxn]; int main()
{
int n,m,i,j,k,ans;
while ( scanf("%d%d",&n,&m)!=EOF )
{
for ( i=;i<=n;i++ ) scanf("%d%lf",&arr[i].s,&arr[i].x);
memset(dp,,sizeof(dp));
ans=;
for ( i=;i<=n;i++ )
{
for ( j=;j<i;j++ )
{
if ( arr[i].s>=arr[j].s ) dp[i]=max(dp[i],dp[j]);
}
dp[i]++;
ans=max(ans,dp[i]);
}
printf("%d\n",n-ans);
}
return ;
}
269B
12.(977F)http://codeforces.com/problemset/problem/977/F
题意：求最长递增子串，要求串中的元素大小是连续的
分析：因为a[i]在[1,1e9]的范围内，所以采用map<>dp，dp[i]表示以i为结尾的最长长度。转移方程为dp[a[i]]=max(dp[a[i]],dp[a[i-1]+1]);
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=2e5+;
map<int,int>dp;
int a[maxn]; int main()
{
int n,i,j,k,x,y,z,m,p,ans,t;
while ( scanf("%d",&n)!=EOF )
{
dp.clear();
ans=;
k=;
for ( i=;i<=n;i++ )
{
scanf("%d",&a[i]);
dp[a[i]]=max(dp[a[i]],dp[a[i]-]+);
if ( dp[a[i]]>ans )
{
ans=dp[a[i]];
k=i;
}
}
t=a[k]-ans+;
printf("%d\n",ans);
for ( i=;i<=n;i++ )
{
if ( a[i]==t )
{
printf("%d",i);
if ( i!=k ) printf(" ");
else
{
printf("\n");
break;
}
t++;
}
}
}
return ;
}
977F
13.(721C)http://codeforces.com/problemset/problem/721/C
题意：给定一个有n个点m条边的有向图，给定初始费用c。初始点在1，结束点在n，每条边都有边权，每经过一条边都要花费边权的费用。先求从起到到终点最多能经过几条边
分析：DAG上的dp，设dp[i][j]表示从1到i这个点，中间经过j座城市的最少时间花费。dp[1][1]=0,其他初始化为Inf（尽可能大）。采用bfs边拓步排序边状态转移，每次将入度为0的点放入栈中。对于边(u,v)，边权为cost的边来说，转移方程为dp[v][j]=min(dp[v][j],dp[u][j-1]+cost) (j为[2,n])，当一个点的入度减为0时再将其放入栈中。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=;
const int inf=0x3f3f3f3f;
struct edge{
int v,cost;
edge(int _v=,int _cost=):v(_v),cost(_cost) {}
};
vector<edge>G[maxn];
int dp[maxn][maxn];
int pre[maxn][maxn],ind[maxn],n;
bool vis[maxn];
vector<int>pos; void bfs()
{
queue<int>que;
dp[][]=;
for ( int i=;i<=n;i++ )
{
if ( !ind[i] )
{
vis[i]=true;
que.push(i);
}
}
while ( !que.empty() )
{
int u=que.front();
que.pop();
for ( int i=;i<G[u].size();i++ )
{
int v=G[u][i].v;
int cost=G[u][i].cost;
if ( ind[v] )
{
ind[v]--;
for ( int j=;j<=n;j++ )
{
if ( dp[v][j]>dp[u][j-]+cost )
{
dp[v][j]=dp[u][j-]+cost;
pre[v][j]=u;
}
}
if ( !ind[v] ) que.push(v);
}
}
}
} int main()
{
int m,c,i,j,k,x,y,z,ans,now,p;
while ( scanf("%d%d%d",&n,&m,&c)!=EOF )
{
for ( i=;i<=n;i++ ) G[i].clear();
for ( i=;i<=n;i++ )
for ( j=;j<=n;j++ ) dp[i][j]=inf;
memset(ind,,sizeof(ind));
memset(vis,false,sizeof(vis));
for ( i=;i<=m;i++ )
{
scanf("%d%d%d",&x,&y,&z);
G[x].push_back(edge(y,z));
ind[y]++;
}
bfs();
ans=;
for ( i=;i<=n;i++ )
{
if ( dp[n][i]<=c ) ans=max(i,ans);
}
printf("%d\n",ans);
pos.clear();
now=n;
p=ans;
while ( p )
{
pos.push_back(now);
now=pre[now][p--];
}
for ( i=pos.size()-;i>=;i-- )
{
printf("%d",pos[i]);
if ( i!= ) printf(" ");
else printf("\n");
}
}
return ;
}
721C
14.(463D)http://codeforces.com/problemset/problem/463/D
题意：给出m个排列，每个排列长度均为n，求最长公共子串
分析：求最长路，具体做法是：以第一个排列为基准，设置bool型的数组line[maxn][maxn],初始化为true，当line[i][[j]=true表示对于所有排列来说i和j的相对位置都是一样的，都与第一个排列相同，这样可以建一条i到j的边（i<j），边长为1。设置起点s=0,终点t=n+1,s到所有点建边长为1的边，所有点到t建边长为0的边。对建好的图跑一次最长路，取反即为最后的答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=;
const int maxm=;
const int inf=1e9;
bool line[maxn][maxn];
int a[maxm][maxn],pos[maxn];
struct edge{
int v,cost;
edge(int _v=,int _cost=):v(_v),cost(_cost) {}
};
vector<edge>G[maxn];
bool vis[maxn];
int dist[maxn]; void addedge(int u,int v,int w)
{
G[u].push_back(edge(v,-w));
} void SPFA(int start,int n)
{
memset(vis,false,sizeof(vis));
for ( int i=;i<=n;i++ ) dist[i]=inf;
vis[start]=true;
dist[start]=;
queue<int>que;
que.push(start);
while ( !que.empty() )
{
int u=que.front();
que.pop();
vis[u]=false;
for ( int i=;i<G[u].size();i++ )
{
int v=G[u][i].v;
int cost=G[u][i].cost;
if ( dist[v]>dist[u]+cost )
{
dist[v]=dist[u]+cost;
if ( !vis[v] )
{
vis[v]=true;
que.push(v);
}
}
}
}
} int main()
{
int n,m,i,j,k,x,y,z,u,v,t,s;
while ( scanf("%d%d",&n,&m)!=EOF )
{
memset(line,true,sizeof(line));
for ( i=;i<=m;i++ )
for ( j=;j<=n;j++ ) scanf("%d",&a[i][j]);
for ( i=;i<=n;i++ ) pos[a[][i]]=i;
for ( k=;k<=m;k++ )
for ( i=;i<=n;i++ )
for ( j=;j<i;j++ )
{
u=pos[a[k][i]];
v=pos[a[k][j]];
if ( v>u ) line[u][v]=line[v][u]=false;
}
s=;
t=n+;
for ( i=;i<=t;i++ ) G[i].clear();
for ( i=;i<=n;i++ )
{
for ( j=i+;j<=n;j++ )
{
if ( line[i][j] ) addedge(i,j,);
}
addedge(s,i,);
addedge(i,t,);
}
SPFA(s,t);
printf("%d\n",-dist[t]);
}
return ;
}
463D
15.（873B）http://codeforces.com/problemset/problem/873/B
题意：给出一段长度为n的01串，定义一段序列平衡，要求该序列中0和个数和1的个数相等，求最长的平衡序列长度有多长
分析：“0”转化为-1，“1”转化为1，记录前缀和。用map记录前缀和每个值第一次出现的位置（特别地mp[0]=0），然后对于位置i有前缀和sum[i]=x，从[1,i]最长的平衡串长度为i-mp[x]，即x第一次出现的位置到i这段的长度。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=1e5+;
char s[maxn];
int sum[maxn],a[maxn];
map<int,int>mp; int main()
{
int n,m,i,j,k,x,y,z,ans,now;
while ( scanf("%d",&n)!=EOF )
{
mp.clear();
scanf("%s",s+);
sum[]=;
for ( i=;i<=n;i++ )
{
if ( s[i]=='' ) a[i]=-;
else a[i]=;
sum[i]=a[i]+sum[i-];
if ( mp[sum[i]]== ) mp[sum[i]]=i;
}
mp[]=;
ans=;
for ( i=;i<=n;i++ )
{
x=sum[i];
y=mp[x];
now=i-y;
ans=max(ans,now);
}
printf("%d\n",ans);
}
return ;
}
873B
16.（479E）http://codeforces.com/problemset/problem/479/E
题意：有一栋大楼，总共有n层，一开始你处于第a层,第b层你是无法到达的，总共有k次坐电梯的机会每次坐电梯你可以从第x层到第y层，但是需要满足x!=y&&|x-b|>|x-y|，求最多有几种坐电梯的方案
分析：设dp[i][j]表示第j次坐电梯到第i层的方案数，dp[i][j]=sum(dp[k][j-1])(k为能一次坐到第i层的层号)。注意当a>b时要维护前缀和,a<b时要维护后缀和
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=;
const ll mod=1e9+;
ll dp[maxn][maxn],sum[maxn]; int main()
{
int n,a,b,m,i,j,k,x,y,z,l,r;
ll ans;
while ( scanf("%d%d%d%d",&n,&a,&b,&m)!=EOF )
{
memset(dp,,sizeof(dp));
memset(sum,,sizeof(sum));
dp[a][]=;
ans=;
if ( b>a )
{
for ( i=;i<b;i++ ) sum[i]=sum[i-]+dp[i][];
for ( k=;k<=m;k++ )
{
for ( i=;i<b;i++ )
{
r=(b+i-)/;
dp[i][k]=(sum[r]-dp[i][k-])%mod;
}
for ( i=;i<b;i++ ) sum[i]=sum[i-]+dp[i][k];
}
for ( i=;i<b;i++ ) ans=(ans+dp[i][m])%mod;
}
else
{
for ( i=n;i>b;i-- ) sum[i]=sum[i+]+dp[i][];
for ( k=;k<=m;k++ )
{
for ( i=n;i>b;i-- )
{
l=(b+i)/+;
dp[i][k]=(sum[l]-dp[i][k-])%mod;
}
for ( i=n;i>b;i-- ) sum[i]=sum[i+]+dp[i][k];
}
for ( i=b+;i<=n;i++ ) ans=(ans+dp[i][m])%mod;
}
printf("%lld\n",ans);
}
return ;
}
479E
17.http://codeforces.com/problemset/problem/687/C
题意：给出n个数，从中取一些数使得他们的和为m。将取出的数看作一个集合，求这个集合的子集元素之和有哪些可能
分析：d[i][j]表示取出集合中的和为i，该集合的子集可能的和为j，最后的答案为d[m][i]==true（0<=i<=m）的i值.
中间的状态转移过程类似于01背包，一个数只能用一次。当值为a[k]时，可以由d[i][j]转移到d[i+a[k]][j]和d[i+a[k]][j+a[k]]。同时注意，三层循环的最外层是每些数的值，第二层要从大到小（保证只能取一个）
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int a[maxn],ans[maxn];
bool d[maxn][maxn],vis[maxn]; int main()
{
int n,m,i,j,k,x,y,z,cnt;
while ( scanf("%d%d",&n,&m)!=EOF )
{
memset(d,false,sizeof(d));
for ( i=;i<=n;i++ ) scanf("%d",&a[i]);
d[][]=true;
for ( k=;k<=n;k++ )
{
for ( i=m;i>=;i-- )
{
for ( j=;j<=i;j++ )
{
if ( !d[i][j] ) continue;
d[i+a[k]][j]=true;
d[i+a[k]][j+a[k]]=true;
}
}
}
cnt=;
for ( i=;i<=m;i++ )
{
if ( d[m][i] ) ans[++cnt]=i;
}
printf("%d\n",cnt);
for ( i=;i<=cnt;i++ )
{
printf("%d",ans[i]);
if ( i!=cnt ) printf(" ");
else printf("\n");
}
}
return ;
}
687C
18.(219D)http://codeforces.com/problemset/problem/219/D
题意：图中有n个城市，n-1条单向边，选一个城市为首都，使得所需要反转的边最少，输出反转边的条数和边的编号
分析：首先对本来已经存在的边建变成为0的边，反向边建变成为1的边。设置dp[2][maxn]，dp[0][i]表示以i为根到所有叶子节点的总路径之和。dp[1][i]表示i到i上半部分所有点的总路径之和。
跑两次dfs，第一次可以求出dp[0][i]。第二次跑dfs，若存在u到v的边长为w的边则有dp[1][v]=dp[0][u]-dp[0][v]-w+dp[1][u]+(w^1) (最后的括号不能落)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=2e5+;
struct edge{
int v,w;
edge(int _v=,int _w=):v(_v),w(_w) {}
};
int dp[][maxn],ans[maxn],cnt[maxn];
vector<edge>G[maxn]; void dfs0(int u,int fa)
{
for ( int i=;i<G[u].size();i++ )
{
int v=G[u][i].v;
int w=G[u][i].w;
if ( v==fa ) continue;
dfs0(v,u);
dp[][u]+=(w+dp[][v]);
}
} void dfs1(int u,int fa)
{
for ( int i=;i<G[u].size();i++ )
{
int v=G[u][i].v;
int w=G[u][i].w;
if ( v==fa ) continue;
dp[][v]=dp[][u]-dp[][v]-w+dp[][u]+(w^);
dfs1(v,u);
}
} int main()
{
int n,i,j,k,x,y,z,u,v,w,res;
while ( scanf("%d",&n)!=EOF )
{
for ( i=;i<=n;i++ ) G[i].clear();
for ( i=;i<n;i++ )
{
scanf("%d%d",&u,&v);
G[u].push_back(edge(v,));
G[v].push_back(edge(u,));
}
memset(dp,,sizeof(dp));
dfs0(,-);
dfs1(,-);
res=n;
for ( i=;i<=n;i++ )
{
ans[i]=dp[][i]+dp[][i];
res=min(ans[i],res);
}
int num=;
for ( i=;i<=n;i++ )
{
if ( ans[i]==res ) cnt[++num]=i;
}
printf("%d\n",res);
for ( i=;i<=num;i++ )
{
printf("%d",cnt[i]);
if ( i!=num ) printf(" ");
else printf("\n");
}
}
return ;
}
219D
20.(710E)http://codeforces.com/problemset/problem/710/E
题意：起初没有字符，要求构造n个a，添加或者删除一个a耗费a单位的时间，成倍添加a耗费b单位的时间
分析：直接从[2,n]一个个遍历过来，i可以由i-1和i/2（若为奇数则为(i+1)/2）转移过来
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e7+;
ll dp[maxn]; int main()
{
int n,a,b,i,j,k,x,y,z;
while ( scanf("%d%d%d",&n,&a,&b)!=EOF )
{
dp[]=;
dp[]=a;
for ( i=;i<=n;i++ )
{
dp[i]=dp[i-]+a;
if ( i& ) dp[i]=min(dp[i],dp[(i+)/]+b+a);
else dp[i]=min(dp[i],dp[i/]+b);
}
printf("%lld\n",dp[n]);
}
return ;
}
710E
21.（255C）http://codeforces.com/problemset/problem/255/C
题意：求一个最长的序列长度，该序列满足a1=p,an=a1+(-1)^(n+1)*q
分析：设dp[i][j]表示该序列最后一项为i，倒数第二项为j，当a[j]==a[k]时dp[k][i]=dp[i][j]+1，本来是n^3的复杂度，但是可以通过一定的方法优化（优化过程见代码），优化的大致就是第一重循环代表i，设置变量k，记录于第i项相等的位置的下标，初始值为-1。第二重循环j从1到i,当k==-1时，即还没有遇到相同的值dp[i][j]=2,否则dp[i][j]=dp[j][k]+1，当遇到a[i]==a[j]时，k==j，因为对于最长的序列来说，于i相等的值距离i越近越好
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int dp[maxn][maxn];
int a[maxn]; int main()
{
int n,m,i,j,k,x,y,z,ans;
while ( scanf("%d",&n)!=EOF )
{
for ( i=;i<=n;i++ ) scanf("%d",&a[i]);
ans=;
for ( i=;i<=n;i++ )
{
k=-;
for ( j=;j<i;j++ )
{
if ( k==- ) dp[i][j]=;
else dp[i][j]=dp[j][k]+;
if ( a[i]==a[j] ) k=j;
ans=max(ans,dp[i][j]);
}
}
printf("%d\n",ans);
}
return ;
}
255C
22.(478D)http://codeforces.com/problemset/problem/478/D
题意：用n个红色块和m个绿色块，去构建一个塔，塔每层的块的数量一定比上一层（第一层只有一个）多一个，同时处于塔的同一层的色块颜色必须相同，求用给定的色块去构建这样的红绿塔，一共有多少种方案。
分析：因为每层的数量是从1每次增加一个的，所以最后的塔的最大高度是确定的（只与数量有关，与颜色无关）（不太会证明..）。所有设dp[i][j]为构建前i层时，总共需要j个绿色色块的数量的方案有多少。
for循环的第一层表示层数，第二层表示j，注意每次枚举j时都要满足红绿色块的要求，dp[i][j]=dp[i-1][j]+dp[i-1][j-i] (j>=i时有后一项)，不满足条件的j下dp[i][j]=0。但是因为所给数据较大会爆空间，考虑到最多只会用到数组的两层，所以考虑弄成滚动数组，即将第一维压成两层。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=4e5+;
const int maxm=;
const ll mod=1e9+;
ll dp[][maxn]; int main()
{
int n,m,i,j,k,x,y,z,h,sz,p;
ll ans;
while ( scanf("%d%d",&n,&m)!=EOF )
{
for ( h=;(+h)*h/<=(n+m);h++ );
h--;
memset(dp,,sizeof(dp));
dp[][]=;
for ( i=;i<=h;i++ )
{
if ( i%== ) x=;
else x=;
sz=(i+)*i/;
p=min(sz,m);
for ( j=;j<=p;j++ ) dp[x][j]=;
for ( j=;j<=p;j++ )
{
int jj=sz-j;
if ( jj>n ) continue;
if ( j>m ) break;
dp[x][j]=dp[-x][j]%mod;
if ( j>=i ) dp[x][j]=(dp[x][j]+dp[-x][j-i])%mod;
}
}
if ( h%== ) x=;
else x=;
ans=;
sz=(+h)*h/;
for ( i=;i<=sz;i++ )
{
if ( sz-i>n ) continue;
if ( i>m ) break;
ans=(ans+dp[x][i])%mod;
}
printf("%lld\n",ans);
}
return ;
}
478D
23.（459E）http://codeforces.com/problemset/problem/459/E
参考此博客：https://blog.csdn.net/qq_24451605/article/details/48877073
题意：给出n个点,m条边的有向图，每个边有边权，求一条最长的边权上升的路径的长度。
分析：先对所有边按权值从小到大进行排序
定义dp[i]表示第i条边结尾的情况下的最长路径。定义g[i]表示点i结尾的情况的最长路径。所以dp[i] = g[e[i].u]+1。然后只需要特殊考虑一下边相等的情况，更新g[i]即可
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=3e5+;
struct Edge{
int u,v,w;
}edge[maxn];
int dp[maxn],g[maxn]; bool cmp(Edge a,Edge b)
{
return a.w<b.w;
} int main()
{
int n,m,i,j,k,x,y,z,t,u,v,w,ans;
while ( scanf("%d%d",&n,&m)!=EOF )
{
memset(dp,,sizeof(dp));
memset(g,,sizeof(g));
t=;
for ( i=;i<=m;i++ ) scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
sort(edge+,edge++m,cmp);
edge[m+].w=;
for ( i=;i<=m;i++ )
{
u=edge[i].u;
v=edge[i].v;
w=edge[i].w;
dp[i]=g[u]+;
if ( edge[i].w!=edge[i+].w )
{
for ( j=t;j<=i;j++ ) g[edge[j].v]=max(g[edge[j].v],dp[j]);
t=i+;
}
}
ans=;
for ( i=;i<=m;i++ ) ans=max(ans,dp[i]);
printf("%d\n",ans);
}
return ;
}
459E
24.（933A）http://codeforces.com/problemset/problem/933/A
题意：给定一串序列只含数字1和2，现在可以选择一段任意长度的序列将它进行反转，求能够得到的最长非递减子序列的长度是多少
分析：因为原串只含数字1和2，所以反转的部分2222211111（连续的1中可能含少许2，连续的2中可能含少许1，忽略不计，下同。类似于这样2在前1在后的部分），而整个序列最有可能的样子是1111222211112222，我们只需要将其中的22221111这部分进行反转就能得到最大的长度。所有我们定义dp[2][n] ,dp[0][i]表示[1,i]上的最长非递减子序列的长度，dp[1][i]表示[i,n]上的最长非递减子序列的长度。这样最后的答案是dp[0][k]+dp[1][k+1](1<=k<=n)中的最大值
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int dp[][maxn];
int a[maxn]; int main()
{
int n,i,j,k,m,x,y,z,ans;
while ( scanf("%d",&n)!=EOF )
{
for ( i=;i<=n;i++ ) scanf("%d",&a[i]);
a[]=a[n+]=;
memset(dp,,sizeof(dp));
for ( i=;i<=n;i++ )
{
dp[][i]=;
for ( j=;j<i;j++ )
{
if ( a[j]<=a[i] ) dp[][i]=max(dp[][i],dp[][j]+);
}
if ( a[i]==a[i-] ) dp[][i]=max(dp[][i],dp[][i-]);
}
for ( i=n;i>=;i-- )
{
dp[][i]=;
for ( j=n;j>i;j-- )
{
if ( a[j]>=a[i] ) dp[][i]=max(dp[][i],dp[][j]+);
}
if ( a[i+]==a[i] ) dp[][i]=max(dp[][i],dp[][i+]);
}
ans=;
for ( i=;i<=n;i++ )
{
if ( dp[][i]+dp[][i+]>ans ) ans=dp[][i]+dp[][i+];
}
printf("%d\n",ans);
}
return ;
}
933A
25.(180C)http://codeforces.com/problemset/problem/180/C
题意：给定一串字符串，字符串只包含大写字母和小写字母，现在我们可以使某一个位置的大写字母变成小写字母，使某一个位置的小写字母变成大写字母，先求最小的操作次数，使得左边全为大写字母，右边全为小写字母。
分析：dp[0][i]记录[1,i]个中有多少的小写字母，dp[1][i]记录[i,n]中有多少个大写字母，枚举分界点，最后ans=min（dp[0][i]+dp[1][i+1]）(0<=i<=n)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+;
char s[maxn];
int dp[][maxn]; int main()
{
int n,i,j,k,x,y,z,ans,cnt0,cnt1;
while ( scanf("%s",s+)!=EOF )
{
n=strlen(s+);
memset(dp,,sizeof(dp));
cnt0=cnt1=;
for ( i=;i<=n;i++ )
{
if ( s[i]>='a' && s[i]<='z' ) cnt0++;
if ( s[n-i+]>='A' && s[n-i+]<='Z' ) cnt1++;
dp[][i]=cnt0;
dp[][n-i+]=cnt1;
}
ans=n;
for ( i=;i<=n;i++ ) ans=min(ans,dp[][i]+dp[][i+]);
printf("%d\n",ans);
}
return ;
}
180C
26.(407B)http://codeforces.com/problemset/problem/407/B
题意：有n+1个房间，刚开始在第1个房间，刚开始第一个房间的墙上有一个X，其他房间没有，每到一个房间都在这个房间的墙上打一个X，当墙上X的个数为奇数时，那么这个人会到第a[i]个房间，当墙上X的个数为偶数时，那么这个人会到第i+1个房间，现在求需要走几步才能到第n+1个房间
分析：dp[i]表示从第0个点第二次走到i需要消耗的时间，初始化dp[1]=2，即假设刚开始在第0个房间，第0个房间只能到第一个房间。
状态转移方程为：dp[i]=(dp[i-1]+1+dp[i-1]-dp[a[i]-1]+1+mod)%mod; dp[i-1]+1为第一次到达需要的时间,dp[i-1]-dp[a[i]-1]+1为第二次到达所需要的时间
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=;
const ll mod=1e9+;
int a[maxn];
ll dp[maxn]; int main()
{
int i,j,k,x,y,z,m,n,ans;
while ( scanf("%d",&n)!=EOF )
{
for ( i=;i<=n;i++ ) scanf("%d",&a[i]);
memset(dp,,sizeof(dp));
dp[]=;
for ( i=;i<=n;i++ )
{
dp[i]=(dp[i-]++dp[i-]-dp[a[i]-]++mod)%mod;
}
printf("%lld\n",dp[n]);
}
return ;
}
407B
27.(163A)http://codeforces.com/problemset/problem/163/A
题意：给定两个串s1,s2,求s1的子串（连续）和s2的子序列（不连续）相同的个数
分析：dp[i][j]表示s1从[1,i]的子串和s2从[1,j]的子序列中相同的个数。
dp[i][j]=dp[i][j-1] (s1[i]!=s2[j])
dp[i][j]=dp[i][j-1]+dp[i-1][j-1]+1 (s1[i]==s2[j])
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=;
const ll mod=1e9+;
ll dp[maxn][maxn];
char s1[maxn],s2[maxn]; int main()
{
int n,m,i,j,k,x,y,z;
ll ans;
while ( scanf("%s%s",s1+,s2+)!=EOF )
{
n=strlen(s1+);
m=strlen(s2+);
memset(dp,,sizeof(dp));
for ( i=;i<=n;i++ )
{
for ( j=;j<=m;j++ )
{
dp[i][j]=dp[i][j-];
if ( s1[i]==s2[j] ) dp[i][j]=(dp[i][j]+dp[i-][j-]+)%mod;
}
}
ans=;
for ( i=;i<=n;i++ ) ans=(ans+dp[i][m])%mod;
printf("%lld\n",ans);
}
return ;
}
163A
28.（936B）http://codeforces.com/problemset/problem/936/B
题意：给定一个有向图，问从s点出发能否走奇数条边到一个没有出度的点。
分析：搜索。设置变量dp[maxn][2]，vis[maxn][2]第二维为0表示走的下一条边为奇数次，第二维为1表示走的下一条边为偶数次。dp[i]代表的是从i出发能发到达一个没有出度的点。vis[i]==1表示到过这个点，但是这个点还未处理完（当搜索过程中遇到其他vis[j]==1的点表示存在环）,vis[i]==2表示这个点已经处理完。最后判断dp[s][0]是否为true即可，若不是再判断有无环
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=2e5+;
bool dp[maxn][];
int vis[maxn][],out[maxn],nxt[maxn][];
vector<int>G[maxn];
bool cir,flag; bool dfs(int u,int op)
{
if ( !out[u] )
{
dp[u][op]=true;
vis[u][op]=;
return op==;
}
if ( vis[u][op]== ) return dp[u][op];
vis[u][op]=;
for ( int i=;i<G[u].size();i++ )
{
int v=G[u][i];
if ( vis[v][-op]== )
{
cir=true;
continue;
}
if ( dfs(v,-op) )
{
dp[u][op]=true;
nxt[u][op]=v;
}
}
vis[u][op]=;
return dp[u][op];
} void print(int u)
{
int op=;
u=nxt[u][];
while ( u!=- )
{
printf(" %d",u);
u=nxt[u][op];
op=-op;
}
} int main()
{
int n,m,i,j,k,x,y,z,s;
while ( scanf("%d%d",&n,&m)!=EOF )
{
for ( i=;i<=n;i++ ) G[i].clear();
memset(out,,sizeof(out));
memset(vis,,sizeof(vis));
memset(dp,false,sizeof(dp));
memset(nxt,-,sizeof(nxt));
cir=false;
for ( i=;i<=n;i++ )
{
scanf("%d",&k);
for ( j=;j<=k;j++ )
{
scanf("%d",&x);
G[i].push_back(x);
out[i]++;
}
}
scanf("%d",&s);
if ( out[s]== )
{
printf("Lose\n");
continue;
}
dfs(s,);
if ( dp[s][] )
{
printf("Win\n");
printf("%d",s);
print(s);
printf("\n");
}
else if ( cir ) printf("Draw\n");
else printf("Lose\n");
}
return ;
}
936B
29.(264C)http://codeforces.com/problemset/problem/264/C
题意：有n个气球，每个气球都有一个价值和一种颜色。现在有q个询问，每次询问给个a、b，让你从原气球中按顺序取出一些气球。对于一个气球若前面一个气球和它的颜色相同那么加上这个气球的值乘a，其他情况（第一个气球或者前一个气球和它颜色不同）加上这个气球的值乘以b，求这个值最大是多少
分析：对于每个询问要单独考虑，设置dp[i]表示对于当前位置往前的所有气球来说取出的气球颜色为i的情况中最多的值是多少，dp初始化为-inf表示不存在
对于一个气球在取出的气球中对整体所加的值的贡献不是a*val[i]就是b*val[i]那么我们分别考虑，
要是a*val[i]，我们就去找前一个和它颜色一样气球即dp[col[i]]+a*val[i]
要是b*val[i]，我们就要使这个气球是第一个气球，或者去找前面和它颜色不同气球中的最大值(即dp[x]max的值且x!=col[i])，这时候我们就应该记录前面气球中的最大值和次大值（要求颜色不同），这样就可以方便的更新了。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
const ll inf=1e17;
ll dp[maxn];
ll val[maxn],col[maxn]; int main()
{
ll n,m,i,j,k,x,y,z,q,a,b,v,c;
ll ans,sum;
while ( scanf("%lld%lld",&n,&q)!=EOF )
{
for ( i=;i<=n;i++ ) scanf("%lld",&val[i]);
for ( i=;i<=n;i++ ) scanf("%lld",&col[i]);
while ( q-- )
{
scanf("%lld%lld",&a,&b);
sum=;
for ( i=;i<=n;i++ ) dp[i]=-inf;
int id1=,id2=;
for ( i=;i<=n;i++ )
{
v=val[i];
c=col[i];
ans=max(b*v,dp[c]+a*v);
if ( id1!=c ) ans=max(ans,dp[id1]+b*v);
else ans=max(ans,dp[id2]+b*v);
if ( ans>dp[id1] )
{
if ( id1!=c )
{
id2=id1;
id1=c;
}
else id1=c;
}
else
{
if ( ans>dp[id2] && c!=id1 ) id2=c;
}
dp[c]=max(dp[c],ans);
sum=max(sum,ans);
}
printf("%lld\n",sum);
}
}
return ;
}
264C
30.（234F）http://codeforces.com/problemset/problem/234/F
题意：给出n个栅栏，需要涂上红色和绿色。红色的面积不能超过啊a，绿色的面积不能超过b。给出每个栅栏的高度，宽度都是1。所得的价值等于相邻栅栏不同颜色的面积。求最小的价值。
分析：首先注意是文件输入，而不是标准的输入输出。设dp[i][j][k]第一维为前i行（可以设置为动态数组，因为只用到两行，但此题没关系），第二维为已经用了几个绿色的面积是多少，第三维为0表示第i行全为红，为1表示第i行全为绿。
转移时dp[i][j][0]=dp[i-1][j][0] (相邻两行都为红)
dp[i][ j+h[i] ][1]=dp[i-1][j][1] (相邻两行都为绿)
dp[i][j][0]=dp[i-1][j][1]+min(h[i],h[i-1]) (前一行为绿，这一行为红)
dp[i][ j+h[i] ][0]=dp[i-1][j][0]+min(h[i],h[i-1]) (前一行为红，这一行为绿)
注意：红色的面积和绿色的面积要满足题目的要求
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<fstream>
using namespace std;
const int maxn=;
const int maxm=4e4+;
const int inf=1e9;
int dp[maxn][maxm][];
int h[maxn],num[maxn];
set<int>st;
set<int>::iterator it; int main()
{
int n,a,b,x,y,z,ans,sum,i,j,k,val;
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&n);
sum=;
num[]=;
scanf("%d%d",&a,&b);
for ( i=;i<=n;i++ )
{
scanf("%d",&h[i]);
sum+=h[i];
num[i]=num[i-]+h[i];
}
if ( sum>(a+b) )
{
printf("-1\n");
return ;
}
ans=inf;
for ( i=;i<=n;i++ )
{
for ( j=;j<=a+b;j++ )
{
for ( k=;k<;k++ ) dp[i][j][k]=inf;
}
}
st.clear();
st.insert();
dp[][][]=dp[][][]=;
for ( i=;i<=n;i++ )
{
for ( it=st.begin();it!=st.end();it++ )
{
x=*it;
val=dp[i-][x][];
if ( val!=inf )
{
if ( x+h[i]<=b )
{
dp[i][x+h[i]][]=min(dp[i][x+h[i]][],val+min(h[i],h[i-]));
st.insert(x+h[i]);
}
if ( num[i]-x<=a ) dp[i][x][]=min(dp[i][x][],val);
}
val=dp[i-][x][];
if ( val!=inf )
{
if ( x+h[i]<=b )
{
dp[i][x+h[i]][]=min(dp[i][x+h[i]][],val);
st.insert(x+h[i]);
}
if ( num[i]-x<=a ) dp[i][x][]=min(dp[i][x][],val+min(h[i],h[i-]));
}
}
}
for ( it=st.begin();it!=st.end();it++ )
{
x=*it;
ans=min(ans,min(dp[n][x][],dp[n][x][]));
}
if ( ans==inf ) printf("-1\n");
else printf("%d\n",ans); return ;
}
234F
31.http://codeforces.com/problemset/problem/404/D
题意：一维的扫雷，"*"表示雷，“0”表示左右两边没有雷，“1”表示左右两边有一个雷，“2”表示左右两个都是雷，“？”表示不确定任意填（但是需要满足左右两个方格内的条件），先求方案数
分析;dp[maxn][5]，第一维为前i个。
假设第一维为i，
第二维为0表示第i位为雷，第i-1位和第i+1位任意。
第二维为1表示第i位没有雷，第i-1位和第i+1位都没有雷。
第二维为2表示第i位没有雷，第i-1位没有雷和第i+1位有雷。
第二维为3表示第i位没有雷，第i-1位有雷和第i+1位没有雷。
第二维为4表示第i位没有雷，第i-1位和第i+1位都有雷。
初始化都为0,dp[0][1]=dp[0][2]=1即第0位没有雷和第-1为没有雷的情况数都为1
转移时根据s[i]内的字符不同有不同的转移方式.
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6+;
const int mod=1e9+;
const int inf=1e9;
int dp[maxn][];
char s[maxn]; int main()
{
int n,m,i,j,k,x,y,z,ans;
while ( scanf("%s",s+)!=EOF )
{
n=strlen(s+);
memset(dp,,sizeof(dp));
dp[][]=dp[][]=;
for ( i=;i<=n;i++ )
{
if ( s[i]=='?' )
{
dp[i][]=((dp[i-][]+dp[i-][])%mod+dp[i-][])%mod;
dp[i][]=(dp[i-][]+dp[i-][])%mod;
dp[i][]=(dp[i-][]+dp[i-][])%mod;
dp[i][]=dp[i-][];
dp[i][]=dp[i-][];
}
else if ( s[i]=='' )
{
dp[i][]=(dp[i-][]+dp[i-][])%mod;
}
else if ( s[i]=='' )
{
dp[i][]=dp[i-][];
dp[i][]=(dp[i-][]+dp[i-][])%mod;
}
else if ( s[i]=='' )
{
dp[i][]=dp[i-][];
}
else if ( s[i]=='*' )
{
dp[i][]=((dp[i-][]+dp[i-][])%mod+dp[i-][])%mod;
}
}
ans=((dp[n][]+dp[n][])%mod+dp[n][])%mod;
printf("%d\n",ans);
}
return ;
}
404D
32.(918D)http://codeforces.com/contest/918/problem/D
题意：给定一个 DAG，每个边的权值为一个字母。两人初始各占据一个顶点（可以重合），轮流移动（沿着一条边从一个顶点移动到另一个顶点），要求每次边上的权值 ≥≥ 上一次的权值。无法移动者输。要求：对所有可能的初始情况，给出一张胜负表。
分析：组合游戏+dp。参考以下这篇文章https://www.cnblogs.com/kkkkahlua/p/8386936.html
特殊情况：两个点都在同一点上，那么先手必输
设置dp[i][j][k]表示先手在第i个点上，后手在第j个点上，上一条边的权值为k下先手能否获胜（能获胜为true，不能获胜为false），设置bool型vis数组判断是否被访问过
每次转移时有点类似与博弈论中的求sg函数，下一步中能走到必败态则该点就是必胜态，下一步无论怎么走都走不到必败态，则该点为必败态.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=;
const int maxm=;
struct Edge{
int v,w;
Edge(int _v=,int _w=):v(_v),w(_w) {}
};
bool dp[maxn][maxn][maxm];
bool vis[maxn][maxn][maxm];
vector<Edge>G[maxn]; int dfs(int u,int v,int w)
{
int x,y,z;
if ( vis[u][v][w] ) return dp[u][v][w];
vis[u][v][w]=true;
if ( u==v ) return false;
bool flag=false;
for ( int i=;i<G[u].size();i++ )
{
x=v;
y=G[u][i].v;
z=G[u][i].w;
if ( z>=w )
{
if ( !dfs(x,y,z) ) flag=true;
}
}
if ( flag ) dp[u][v][w]=;
else dp[u][v][w]=;
return dp[u][v][w];
} int main()
{
int n,m,i,j,k,x,y,z,u,v,w;
char s[];
while ( scanf("%d%d",&n,&m)!=EOF )
{
for ( i=;i<=n;i++ ) G[i].clear();
memset(dp,false,sizeof(dp));
memset(vis,false,sizeof(vis));
for ( i=;i<=m;i++ )
{
scanf("%d%d%s",&u,&v,s);
w=s[]-'a'+;
G[u].push_back(Edge(v,w));
}
for ( i=;i<=n;i++ )
{
for ( j=;j<=n;j++ ) dfs(i,j,);
}
for ( i=;i<=n;i++ )
{
for ( j=;j<=n;j++ )
{
if ( dp[i][j][] ) printf("A");
else printf("B");
}
printf("\n");
}
}
return ;
}
918D
33.(918C)http://codeforces.com/contest/918/problem/C
题意：找符合要求的区间个数
分析：
一般的括号匹配
bool check(string s)
{
int top=;
for ( int i=;i<s.size();i++ )
{
if ( s[i]=='(' ) top++;
else top--;
if ( top< ) break;
}
return top==;
}
一般的括号匹配
因为此题出现了“?”可以任意替代，所以采用维护一般括号匹配中top的范围（上届为high，下届为low），枚举区间长度，不断累加符合要求的区间数
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
char s[maxn]; int main()
{
int n,m,i,j,k,x,y,z,ans,low,high;
while ( scanf("%s",s+)!=EOF )
{
n=strlen(s+);
ans=;
for ( i=;i<=n;i++ )
{
low=high=;
for ( j=i;j<=n;j++ )
{
if ( s[j]=='(' ) low++,high++;
else if ( s[j]==')' ) low--,high--;
else low--,high++;
if ( high< ) break;
if ( low< ) low=;
if ( (j-i)& && low== ) ans++;
}
}
printf("%d\n",ans);
}
return ;
}
918C
34.(213C)http://codeforces.com/problemset/problem/213/C
题意：有n*n的方格，每个格子有一个数字，现在有两个人一个人从(1,1)走到（n,n）（但是他只能向右或者向下走）另外一个人从(n,n)走到（1,1）(他只能向左或者向上走),两个人每走到一个格子上就会累加上该格子内的分数，两个人走到同一个格子内时分数只累加一次
分析：该问题等效成两个人都从(1,1)出发往(n,n)走，因为只能往右或者往下走，所以走的步数，横坐标，纵坐标，三个中知道两个就能全部知道。所以设置dp[i][j][k]表示这两个人都走了i步，第一个人在第j行，第二个人在第k行所得到的最大分数。注意如果两个人会走到同一个格子上，那么这两个人一定是同时走到的。
考虑四种情况（往右往下分别组合）.转移时只有当j==k时才加一个格子的数，否则都加两个格子的数
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
const int maxm=;
const int inf=1e9;
int a[maxn][maxn];
int dp[maxm][maxn][maxn];
int dir[][]={{,},{,},{,},{,}}; int main()
{
int n,m,i,j,k,h,x,y,z,dx1,dx2,x1,x2,dy1,dy2;
while ( scanf("%d",&n)!=EOF )
{
for ( i=;i<=*n;i++ )
{
for ( j=;j<=n;j++ )
{
for ( k=;k<=n;k++ ) dp[i][j][k]=-inf;
}
}
for ( i=;i<=n;i++ )
{
for ( j=;j<=n;j++ ) scanf("%d",&a[i][j]);
}
dp[][][]=a[][];
for ( i=;i<=*n-;i++ )
{
for ( j=;j<=n;j++ )
{
for ( k=;k<=n;k++ )
{
for ( h=;h<;h++ )
{
dx1=j+dir[h][];
dx2=k+dir[h][];
dy1=i-dx1+;
dy2=i-dx2+;
if ( dy1< || dy1>n || dy2< || dy2>n || dx1< || dx1>n || dx2< || dx2>n || dp[i-][j][k]==-inf ) continue;
if ( dx1==dx2 ) dp[i][dx1][dx2]=max(dp[i][dx1][dx2],dp[i-][j][k]+a[dx1][dy1]);
else dp[i][dx1][dx2]=max(dp[i][dx1][dx2],dp[i-][j][k]+a[dx1][dy1]+a[dx2][dy2]);
}
}
}
}
printf("%d\n",dp[*n-][n][n]);
}
return ;
}
213C
35.(10D)http://codeforces.com/problemset/problem/10/D
题意：给定两个串求最长公共上升子序列
分析：经典dp题。详细介绍见：http://www.cnblogs.com/sasuke-/p/5396843.html
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int a[maxn],b[maxn];
int dp[maxn],pre[maxn]; void print(int x)
{
if ( x== ) return;
print(pre[x]);
printf("%d ",b[x]);
} int main()
{
int n,m,i,j,k,x,y,z,ans,ans2,pos;
while ( scanf("%d",&n)!=EOF )
{
for ( i=;i<=n;i++ ) scanf("%d",&a[i]);
scanf("%d",&m);
for ( i=;i<=m;i++ ) scanf("%d",&b[i]);
memset(dp,,sizeof(dp));
memset(pre,,sizeof(pre));
for ( i=;i<=n;i++ )
{
pos=;
for ( j=;j<=m;j++ )
{
if ( a[i]==b[j] )
{
dp[j]=dp[pos]+;
pre[j]=pos;
}
if ( a[i]>b[j]&&dp[pos]<dp[j] ) pos=j;
}
}
ans=ans2=;
for ( i=;i<=m;i++ )
{
if ( dp[i]>ans2 )
{
ans2=dp[i];
ans=i;
}
}
printf("%d\n",ans2);
print(ans);
printf("\n");
}
return ;
}
10D
36.（587B）http://codeforces.com/problemset/problem/587/B
题意：给出一个有l个数的序列，序列每n个数一循环，在每个循环里取一个数，最多取m个数，要使得取出的子序列递增，求方案数。
分析：DP，dp[i][j]第一维表示取的是第i个，第二维表示最后一个数的下标编号为j，可以得到转移方程 dp[i][j]=sum(dp[i-1][k]) (a[k]<=a[j])
设置sum[i](1<=i<=m)表示第i层所有的方案数之和（因为此题需要用到前缀和）,f[i]表示最后一项所选的下标编号是i(0<=i<n*m)的方案数。
f[i]=sum[i/n-1]即对于当前的i来说方案数为上一层满足条件的方案数之和（所以在操作前需要排序）
然后更新sum[i/n],sum[i/n]+=f[i]
当i<L时，该值是有效的。ans+=f[i]*[(l-i-1)/n+1] 所表示的含义是满足结尾是i(长度为i/n)这样的情况数有[(l-i-1)/n+1] （减一是因为所以数的下标是从0开始的，l-i-1是要求出后面区间的长度,除n表示有多少个同等情况存在,加一表示本身这种情况）那么多倍。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+;
const ll mod=1e9+;
ll a[maxn],f[maxn],sum[maxn];
pair<ll,ll>p[maxn]; void plu(ll &x,ll y)
{
x=(x+y)%mod;
} int main()
{
ll n,l,m,x,y,z,ans,cnt;
int i,j,k;
while ( scanf("%lld%lld%lld",&n,&l,&m)!=EOF )
{
for ( i=;i<n;i++ ) scanf("%lld",&a[i]);
for ( i=;i<n*m;i++ ) p[i]=make_pair(a[i%n],i);
sort(p,p+n*m);
ans=;
memset(sum,,sizeof(sum));
memset(f,,sizeof(f));
for ( i=;i<n*m;i++ )
{
if ( p[i].second<n ) f[p[i].second]=;
else f[p[i].second]=sum[p[i].second/n-];
plu(sum[p[i].second/n],f[p[i].second]);
if ( p[i].second<l )
{
plu(ans,(f[p[i].second]*(((l-p[i].second-)/n)%mod+)%mod));
}
}
printf("%lld\n",ans);
}
return ;
}
587B
最新文章
- sqoop:Failed to download file from http://hdp01:8080/resources//oracle-jdbc-driver.jar due to HTTP error: HTTP Error 404: Not Found
- Java集合排序（看完秒懂）
- HTTP协议中的1xx，2xx，3xx，4xx，5xx状态码分别表示什么，列举常见错误码及含义
- 2014web面试题
- 在.NET Core中处理一个接口多个不同实现的依赖注入问题
- Dear Menuhin
- 移动端和PC端页面常用的弹出层
- Spring事物管理--相关要点及配置事物管理器
- 为网站添加emoji表情的支持
- JS中sort()方法原理及使用
- datafile相关（add、rename、drop）
- log4j.properties的配置详解
- 插件式程序开发及其应用（C#）
- 再有人问你synchronized是什么，就把这篇文章发给他
- 深入理解JS对象和原型链
- ZT 段祺瑞终生忏悔枪杀学生？
- Android基站定位
- hadoop2.5.2学习及实践笔记（三）—— HDFS概念及体系结构
- 提高mysql千万级大数据SQL查询优化30条经验
- HDU 4336 Card Collector：状压 + 期望dp