一道常规的dp题，注意位于最后一行和位于第一列dp需要特判，然后如果是不能走的地方，就让dp[]=0 #include <bits/stdc++.h> using namespace std; const int mod=2333; template<class T>inline void read(T &res) { char c;T flag=1; while((c=getchar())<'0'||c>'9') if(c=='-') flag=-1;res=c-'0'; while((c=getchar())>='0'&&c...

状态转移方程非常简单，dp[i]=min(dp[i],dp[j]+b[i])然而L高达10的9次方，但是石头的个数只有最多100个，有效的石头数目很少，但是他们分布的空间很广，符合离散化的特点，所以这道题是离散化dp 首先，这道题没有说石头的位置是按顺序输入的，所以要先对石头进行升序排序。接下来就进行离散化操作（自己想用map搞，想了半天没想明白怎么弄，一直WA，后来看了一下别人的离散化方法，恍然大悟，接下来来解释一下） 遍历石头的位置数组，这里记作a[]离散化处理之前石头的位置（输入的是多少就是多少）在这里称为真实位置离散化处理之后石头的位置（进行处理，把范围进行缩小之后）在这里称为理想位置...

首先不考虑马的情况。那么每一个位置，都可以从他的上方走来，和从他的左边走来。那么很容易想到状态转移方程dp[i][j]=dp[i-1][j]+dp[i][j-1]由于多了一个马，那么记录这个马控制的九个点，在对应的vis数组进行标记如果vis[i][j]==1，那么就让dp[i][j]=0，else dp[i][j]=dp[i-1][j]+dp[i][j-1]注意边界条件，卒子在第一行的时候，只能是从左边移动而来，卒子在第一列的时候，只能是从上面移动而来。最后输出dp[n][n]即可 #include <bits/stdc++.h> using namespace std; #de...

每行输入i个数，直接让j从1遍历到i即可，然后用一个cnt表示需要输出的数字。 #include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d",&n); int cnt=0; for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { printf("%4d",++cnt); } printf("\n"); } }

将字符串变成原来的两倍，即s=s+s，然后枚举长度小于等于n的子串，对子串进行马拉车算法，不断更新ans的值。 #include <bits/stdc++.h> using namespace std; string s; string str; int p[10050]; void getstr(int l,int r) { str.clear(); str.push_back('$'); for(int i=l;i<r;i++) { str.push_back('#'); str.push_back(s[i]); } str.push_back('#'); } void ...

dp[j][k]用于表示j到k的闭区间，然后逆向扩展区间，从最后一次取数一直扩展到第一次取数。第一次取数的位置一定为最左或最右，即dp[1][n]=max(dp[2][n]+取数,dp[1][n-1]+取数）。问题得到解决。 #include <bits/stdc++.h> using namespace std; #define ll long long ll dp[1050][1050]; ll a[1050]; ll b[1050]; int main() { int t; scanf("%d",&t); while(t--) { memset(dp,0,sizeof...

问题：n个人围成一个圈，从第一个人传球m次，每次能传给相邻的人，问有多少种方法经过m次传回给第一个人。思考：在第m次的时候传至第一个人手里，那么在m-1次的时候在第二个人或最后一个人手里。用dp[i][j]表示第j次传球，传到第i个人手里的情况有多少种。从而得到状态转移方程：dp[i][j]=dp[i-1][j-1]+dp[i+1][j-1]（若i==1，则i-1改为n；若i==n,则i+1改为1）从而问题得到求解。 #include <bits/stdc++.h> using namespace std; int dp[33][33]; int main() { int n,m;...

用一个二维数组dp[i][j]来表示工作i天，连续工作j天那么得到状态转移方程dp[i][j]=(dp[i-1][j-1])+j （如果当前字符为'1'）最终只要遍历dp数组，找到最长天数ans（并且它满足dp[i][j]<=K，即题目中说的总体力消耗不超过K） #include <bits/stdc++.h> using namespace std; int dp[410][410]; const int INF=0x3f3f3f3f; char s[410]; int main() { int n,m; scanf("%d%d",&n,&m); cin&g...

将问题转化为wavator拿的苹果质量尽可能多，则变成一个容量为sum>>1的背包问题。由于题目要求的是质量尽可能多，那么w[i]等价于v[i]套用01背包模板，注意dp数组的大小至少要开到sum>>1 #include <bits/stdc++.h> using namespace std; int a[5050]; int dp[5050];//维护当前到第几个数，差值 int main() { int sum=0; int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&amp...

一开始的思路是这样的，安排两个人走，第一个人走的时候保证他拿的是最大化的，并且将走过的路全部置为0，再让第二个人走，保证最大，将两个人走过的数全部加起来，就是最后的答案，代码如下： #include <bits/stdc++.h> using namespace std; int a[15][15]; int dp[15][15]; bool dir[15][15];//用于表示从上面走来还是从左边走来，0表示从上面，1表示从左边 int dp2[15][15]; int main() { int n; scanf("%d",&n); int x,y,num; while(...

设石子总数为n所求问题：1到n这些石子合并最少需要多少代价由于石子合并的顺序可以任意，我们将石子分为两个部分子问题：1到k这堆石子合并，k+1到n这堆石子合并，再把两堆石子合并，需要多少代价（1<=k<=n） 那么便可以得到状态转移方程 dp[i][j]=min(dp[i][k]+dp[k+1][j]+……)i到j这些石子合并，代价不仅仅是分开的两堆内部合并的代价，还有两堆石子相互合并的所带来的代价消耗，可得出省略号中的答案为a[i]+a[i+1]+……+a[j]为了加快效率，我们设立一个sum数组来记录前缀和，那么可得到完整的状态转移方程： dp[i][j]=min(dp[i][...

思路：枚举可能的答案，由于题目要求的是求最小，从小到大开始枚举，最小可能是数组里最大的数，最大可能是数组里面所有数的总和。拼接木棍的过程使用dfs，每次拼接一定找未使用过的最大的木棍进行拼接 做到以上，即可保证答案正确，但是速度还不够，需要进行剪枝。 剪枝1：如果当前小木棍是拼接的整个木棍中的第一个或最后一个，那么换用木棍不可能拼接成功剪枝2：如果a[I]==a[I+1] 即换用一个相同大小的木棍，那么必不可能拼接成功，直接跳过，无须尝试拼接有以上两个剪枝即可达到运行时间要求，AC本题 注意事项：每次进行dfs之前需要将相应vis数组置为true，在之后将其置为false，进行回溯。 下面是附...

首先考虑New操作在没有delect的情况下得到的ID是依次加一的，用cnt来表示最新ID，有了delect操作后，ID会存在一个缺口，该缺口用优先队列的最小堆来完成，每次New弹出队顶元素，如果队列为空，则输出++cnt，否则弹出队顶并且输出。 #include <bits/stdc++.h> using namespace std; priority_queue <int,vector<int>,greater<int> > q; int book[100100]; int main() { int n; scanf("%d",&n)...

A题：思路：找规律吧，首先假设没有石墩，那么包括左岸在内，青蛙能够落脚的位置就有荷叶数+1（+1是包含左岸），青蛙按序号依次跳到右岸，那么ans=m+1现在有若干个石墩，给青蛙提供落脚点，令n=1，n=2，n=3……很快就能发现，ans成倍数增长，那么利用二进制的左移（<<）便可以快速得到答案。代码： #include <bits/stdc++.h> using namespace std; int main() { long long n,m; scanf("%lld%lld",&n,&m); long long ans=m+1; ans<&lt...