0-1背包问题； #include<iostream> #include<cstdio> using namespace std; const int maxm=1001; const int maxn=101; int dp[maxm]; int price[maxn]; int point[maxn]; int main(){ int C,N; while(~scanf("%d%d",&C,&N)){ for(int&nbsp...

最长上升子序列和的变体。 #include<iostream> using namespace std; const int maxn=1001; int A[maxn]; int dp[maxn]; int main(){ int n; while(cin>>n){ for(int i=0;i<n;i++){ cin>>A[i]; } int maximum=0; for(int i=0;i<n;i...

此动态规划的状态转移方程为dp[i]=max{1, dp[j]+1 | j<i && A[j]>A[i]}. #include<iostream> using namespace std; int height[26]; int dp[26]; int main(){ int k; while(cin>>k){ for(int i=0;i<k;i++){ cin>>height[i]; } int answer=0;...

先计算一个列和矩阵total，用于快速计算i-j列和（i-j列和[k]=total[j][k]-total[i-1][k]） 形成一个i-j列和数组arr后运用动态规划计算最大子序列， 最后遍历i，j后取得最大子矩阵。 #include<iostream> using namespace std; const int maxn=101; int matrix[maxn][maxn]; int total[maxn][maxn]; //辅助数组，记录列和  int arr[maxn]; ...

注意本题数据较大，需要用到 long long 类型(long 类型与 int 类型 都为四字节，因此范围相同) #include<iostream> using namespace std; const int maxn=1000001; long long N[maxn]; long long dp[maxn]; long long getmaxdp(int n){ dp[0]=N[0]; int i=1; while(i<n){ if...

略微思考可以发现，想要抵达目标台阶n；仅有两种方法， 1.从n-1阶进一步； 2.从n-2阶进两步。（为什么n-2阶不可以进两个一步，因为n-2阶处进一步就抵达了n-1阶（此为第一种情况）） 可以得到 {               f[1]=1         f[2]=2  &n...

看到题目标签中为贪心+二分。想了想当n较大时用二分快一点。 #include<iostream> #include<string> #include<algorithm> using namespace std; const int maxn=1000; const int maxm=5000; string Start[maxn]; bool flag[maxn]; string Target[maxm]; int main(){ int&nbs...