下面再放三道我比較喜歡的，需要好好寫一下的題。
第一題比較水
1. White Cloud is exercising in the playground. White Cloud can walk 1 meters or run k meters per second. Since White Cloud is tired,it can't run for two or more continuous seconds. White Cloud will move L to R meters. It wants to know how many different ways there are to achieve its goal. Two ways are different if and only if they move different meters or spend different seconds or in one second, one of them walks and the other runs.
輸入描述： The first line of input contains 2 integers Q and k.Q is the number of queries.(Q<=100000,1<=k<=100000) For the next Q lines,each line contains two integers L and R.(1<=L<=R<=100000)
輸出描述： For each query,print a line which contains an integer,denoting the answer of the query modulo 1000000007.
示例1: 輸入 3 3 3 3 1 4 1 5 輸出 2 7 11
題目大意
白云在健身，每秒可以走1米或跑k米，并且不能連續兩秒都在跑。 當它的移動距離在[L,R]之間時，可以選擇結束鍛煉。 問有多少種方案結束。
做法
DP? f[i][0/1]表示已經過了i米，最后一步是跑還是走的方案數，分開就很好寫了，簡單，自己體會。 f[i][1]=f[i-k][0],f[i][0]=f[i-1][0]+f[i-1][1] 。注意要記錄前綴和。
?
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll g[100005];
ll dp[100005][2];
int main(void)
{int q,k,a,b;ll sum;cin>>q>>k;dp[0][0]=1;for(int i=1;i<=100000;++i){dp[i][0]=(dp[i-1][0]+dp[i-1][1])%MOD;if(i-k>=0)dp[i][1]=(dp[i-k][0])%MOD;}sum=0;for(int i=1;i<=100000;++i){g[i]=(dp[i][0]+dp[i][1]+sum);sum=g[i];}// for(int i=9000;i<=100000;++i){// cout<<g[i]<<endl;// }while(q--){cin>>a>>b;cout<<(g[b]-g[a-1])%MOD<<endl;}return 0;
}?
2、來一發多重背包
選這個題是感覺代碼有一種美感。。。。。
一. 編程題
1. Since then on, Eddy found that physics is actually the most important thing in the contest. Thus, he wants to form a team to guide the following contestants to conquer the PACM contests(PACM is short for Physics, Algorithm, Coding, Math).
There are N candidate groups each composed of pi physics experts, ai algorithm experts, ci coding experts, mi math experts. For each group, Eddy can either invite all of them or none of them. If i-th team is invited, they will bring gi knowledge points which is calculated by Eddy's magic formula. Eddy believes that the higher the total knowledge points is, the better a team could place in a contest. But, Eddy doesn't want too many experts in the same area in the invited groups. Thus, the number of invited physics experts should not exceed P, and A for algorithm experts, C for coding experts, M for math experts.
Eddy is still busy in studying Physics. You come to help him to figure out which groups should be invited such that they doesn't exceed the constraint and will bring the most knowledge points in total.
輸入描述： The first line contains a positive integer N indicating the number of candidate groups. Each of following N lines contains five space-separated integer p i, ai, ci, mi, gi indicating that i-th team consists of pi physics experts, ai algorithm experts, ci coding experts, mi math experts, and will bring gi knowledge points. The last line contains four space-separated integer P, A, C, M indicating the maximum possible number of physics experts, algorithm experts, coding experts, and math experts, respectively.
?1 ≤ N ≤ 36 0 ≤ pi,ai,ci,mi,gi ≤ 36 0 ≤ P, A, C, M ≤ 36
輸出描述： The first line should contain a non-negative integer K indicating the number of invited groups. The second line should contain K space-separated integer indicating the index of invited groups(groups are indexed from 0).
You can output index in any order as long as each index appears at most once. If there are multiple way to reach the most total knowledge points, you can output any one of them. If none of the groups will be invited, you could either output one line or output a blank line in the second line.
題干有點長，其實就是每個隊有四種代價，一個價值。多重背包。36的五次方竟然沒超時也是醉了。。
?
#include <bits/stdc++.h>
using namespace std;
const int N=37;
int n, p[N], a[N], c[N], m[N], g[N];
int P, A, C, M;
short dp[N][N][N][N][N];
bool tk[N][N][N][N][N];
int main(){cin>>n;for(int i=0; i<n; i++)cin>>p[i]>>a[i]>>c[i]>>m[i]>>g[i];cin>>P>>A>>C>>M;for(int i=0; i<=n; i++)for(int ip=0; ip<=P; ip++)for(int ia=0; ia<=A; ia++)for(int ic=0; ic<=C; ic++)for(int im=0; im<=M; im++)tk[i][ip][ia][ic][im]=false;for(int i=0; i<n; i++){for(int ip=P; ip>=0; ip--)for(int ia=A; ia>=0; ia--)for(int ic=C; ic>=0; ic--)for(int im=M; im>=0; im--)dp[i+1][ip][ia][ic][im]=dp[i][ip][ia][ic][im];for(int ip=P; ip>=p[i]; ip--)for(int ia=A; ia>=a[i]; ia--)for(int ic=C; ic>=c[i]; ic--)for(int im=M; im>=m[i]; im--)if(dp[i][ip-p[i]][ia-a[i]][ic-c[i]][im-m[i]]+g[i]>dp[i+1][ip][ia][ic][im]){dp[i+1][ip][ia][ic][im]=dp[i][ip-p[i]][ia-a[i]][ic-c[i]][im-m[i]]+g[i];tk[i+1][ip][ia][ic][im]=true;}}fprintf(stderr, "ans=%d\n", dp[n][P][A][C][M]);vector<int> ans;for(int i=n; i>=1; i--)if(tk[i][P][A][C][M]){ans.push_back(i-1);P-=p[i-1];A-=a[i-1];C-=c[i-1];M-=m[i-1];}reverse(ans.begin(), ans.end());printf("%d\n", (int)ans.size());for(size_t i=0; i<ans.size(); i++)printf("%d%c", ans[i], " \n"[i+1==ans.size()]);
}
3、P1040 加分二叉樹
題目
https://www.luogu.org/problemnew/show/P1040
設一個?nn?個節點的二叉樹tree的中序遍歷為（?1,2,3,…,n1,2,3,…,n?），其中數字?1,2,3,…,n1,2,3,…,n?為節點編號。每個節點都有一個分數（均為正整數），記第?ii?個節點的分數為?di,treedi,tree?及它的每個子樹都有一個加分，任一棵子樹?subtreesubtree?（也包含?treetree?本身）的加分計算方法如下：
subtreesubtree?的左子樹的加分×?subtreesubtree?的右子樹的加分＋?subtreesubtree?的根的分數。
若某個子樹為空，規定其加分為?11?，葉子的加分就是葉節點本身的分數。不考慮它的空子樹。
試求一棵符合中序遍歷為（?1,2,3,…,n1,2,3,…,n?）且加分最高的二叉樹?treetree?。要求輸出；
（1）?treetree?的最高加分
（2）?treetree?的前序遍歷
思路：這個題可以用動態規劃或者記憶化搜索來做。因為如果要求加分最大的話，必須要求它的兒子結點加分最大，所以就有了最優子階段。我們可以枚舉根來更新最大值。
root[i,j]表示[i,j]這段序列的根，遞歸輸出先序遍歷。注意初始化，f[i][i]=v[i]，當序列只有I一個元素時，f[i][i]等于這個點本身的權值，當l==r-1時，此時是空樹設為1。
?
#include<iostream>
#include<cstdio>
using namespace std;
int n,v[39],f[47][47],i,j,k,root[49][49];
void print(int l,int r){if(l>r)return;if(l==r){printf("%d ",l);return;}printf("%d ",root[l][r]);print(l,root[l][r]-1);print(root[l][r]+1,r);
}
int main() {scanf("%d",&n);for( i=1; i<=n; i++) scanf("%d",&v[i]);for(i=1; i<=n; i++) {f[i][i]=v[i];f[i][i-1]=1;}for(i=n; i>=1; i--)for(j=i+1; j<=n; j++)for(k=i; k<=j; k++) {if(f[i][j]<(f[i][k-1]*f[k+1][j]+f[k][k])) {f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];root[i][j]=k;}}printf("%d\n",f[1][n]);print(1,n);return 0;
}?
?
?
?
?
?
?
?
