动态规划与模拟
月考核总结
- 1.倒序打印三角形
- 2.棋盘走法
- 3.瓶盖换汽水
- 4.蛇形矩阵
- 5.传球游戏
- 6.分糖果
1.倒序打印三角形
我的通过代码： 总体思路是找到第一个打印的数与n的关系（first=n*(n+1)/2）。第一行最多有n个数 ，之后n--,找一个数保存最大列，然后答案印完一行，列数就减一。
#include <stdio.h> #define N 100 int main () { int n,row,col,i,j,a[N][N]; scanf("%d",&row); col=row; for(i=1;i<=row;i++) { n = col*(col+1)/2; for(j=1;j<=col;j++) { if(j==col) printf("%d\n",n); else printf("%d ",n); n--; } col--; } return 0; }
缺点：虽然容易想到吧，但是执行时间太长.... 这不，找到了个执行时间短一点的，注意列可以与行产生“关系”！代码如下：
#include <iostream> using namespace std; int main () { int n,i,j,sum; cin >> n; sum = n*(n+1)/2; //第一个打印的数 for(i=0;i<n;i++) //控制行 { for(j=n-i;j>0;j--) //j=n-i,就动态的把列数给减小了，简直不要太nice { cout << sum; if(j>1) cout << " "; sum--; } cout << endl; } return 0; }
2.棋盘走法
题目描述：
先将第一行的值赋为1，因为只能向下或者向右，所以从（0,0）开始到第一行， 只能有一种走法。（每个数组里面的值代表着走法）右下角的格子的走法等于其 左边的走法加上其上边的走法。即： a[i][j]=a[i-1][j]+a[i][j-1]；
代码如下：
#include <iostream> #include <cstdio> #define N 400 using namespace std; int main () { int a[N][N],i,j,n; cin >> n; for(i=0;i<n;i++) { a[0][i]=1; } for(i=1;i<n;i++) { //注意i=1 for(j=i;j<n;j++) { //j=i a[i][j]=a[i-1][j]+a[i][j-1]; } } cout << a[n-1][n-1]; return 0; }
3.瓶盖换汽水
代码如下：
注意 ：重要的是先理清一种情况下的最大可乐数，那个sum函数里面的while循环 要好好的理清楚，参数比较多，脑壳子不清醒的话就绕进去了.....
#include <iostream> #include <algorithm> using namespace std; int n,x,y; //本函数只解决一种情况下，即a瓶普通可乐，b瓶青柠可乐，最终能喝到的可乐数 int sum(int a,int b) { //普通可乐a瓶，青柠可乐b瓶 int ans=n; //刚开始买了 n瓶 int coke1,coke2; while(a>=x || b>=y){ coke1 = a/x; //该普通可乐a瓶的a个瓶盖最多能换coke1瓶青柠味的可乐 coke2 = b/y; ans += coke1+coke2; a = a%x + coke2; //a%x是剩下未用的瓶盖，加上第一次换了之后的普通可乐（有coke2瓶）的瓶盖 b = b%y + coke1; } return ans; } int solve() { cin >> n >> x >> y; int ans = 0; for(int i=0;i<=n;i++) { ans = max(ans,sum(i,n-i)); //sum(i,n-i)即i瓶普通，n-i瓶青柠，用一个循环找到所有可能中的最大值 } cout << ans << endl; } int main () { int times; cin >> times; //有times组测试 while(times--) { solve(); } return 0; }
4.蛇形矩阵
先复制粘贴一波：
核心仍然在for循环里面，感觉十分巧妙的利用了x和y
#include <bits/stdc++.h> #pragma GCC optimize(3,"Ofast","inline") #define re register #define ll long long #define ull unsigned long long #define r read() using namespace std; //速读 inline int read() { int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } int mp[105][105]; int cnt = 0; int main() { ios::sync_with_stdio(false); int n = r; //上三角 for(int i = 1;i <= n; i++){ if(i % 2){ for(int x = 1, y = i; x <= i && y >= 1; x++, y--){ mp[x][y] = ++cnt; } }else{ for(int y = 1, x = i; y <= i && x >= 1; y++, x--){ mp[x][y] = ++cnt; } } } for(int i = n-1;i >= 1; i--){ if(i % 2){ for(int x = n - i + 1, y = n; x <= n; x++, y--){ mp[x][y] = ++cnt; } }else{ for(int y = n - i + 1, x = n; y <= n; y++, x--){ mp[x][y] = ++cnt; } } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ cout<<mp[j][i]; if(j != n){ cout<<" "; } } cout<<endl; } return 0; }
接下来第二种上代码：
#include <iostream> #include <cstdio> using namespace std; int a[200][200]; int main () { int n,num=1,flag=0; cin >> n; //先打印上三角 for (int i=1;i<=n;i++) { if(flag==0) { for(int j=1;j<=i;j++) { a[i-j+1][j] = num++; } flag = 1; } else { for(int j=1;j<=i;j++) { a[j][i-j+1] = num++; } flag = 0; } } for(int i=n+1;i<2*n;i++) { int t = 2*n-i; if (flag==0) { for (int j=i-n+1;j<i-n+1+t;j++){ a[i-j+1][j]=num++; } flag = 1; } else { for (int j=i-n+1;j<i-n+1+t;j++){ a[j][i-j+1]=num++; } flag = 0; } } for(int i=1;i<n;i++) { for (int j=1;j<n;j++) printf("%d ",a[i][j]); printf("%d\n",a[i][n]); } for(int j=1;j<n;j++) { printf("%d ",a[n][j]); } printf("%d",a[n][n]); return 0; }
我们注意到是以中间的对角线为分隔线开始打印，
还有一种解法（C语言），这个好理解：
#include <stdio.h> int main () { int n,N,i,j,k=0,a[100][100]; scanf("%d",&n); N=1; //以1 开始打印 int m=2*(n-1); //最后一行行和列相加等于2*（n-1） for(k=0;k<=m;k++) { if(k%2==0 && k<n) { //k<n即左上三角 for(i=0;i<=k;i++,N++) a[k-i][i]=N; //k+i + i = k, } else if (k%2==1 && k<n) { for(i=0;i<=k;i++,N++) a[i][k-i]=N; } else if (k%2==0 && k>=n) { for(i=n-1;i>k-n;i--,N++) a[i][k-i]=N; } else if (k%2==1 && k>=n) { for(i=n-1; i>k-n; i--,N++) a[k-i][i]=N; } } for(i=0;i<n;i++) { for(j=0;j<n;j++){ printf("%d",a[i][j]); if(j<n-1) printf(" "); } printf("\n"); } return 0; }
5.传球游戏
动态规划，很显然我还不是很了解下面的代码是啥意思...待我学成归来在回顾这一题
#include <bits/stdc++.h> #pragma GCC optimize(3,"Ofast","inline") #define re register #define ll long long #define ull unsigned long long #define r read() using namespace std; //速读 inline int read() { int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } ull dp[999][2]; int main() { ios::sync_with_stdio(false); int n = r; dp[1][0] = 3; for(int i = 2; i <= n; i++){ dp[i][1] = dp[i-1][0]; dp[i][0] = dp[i-1][0] * 2 + dp[i-1][1] * 3; } cout<<dp[n][1]; return 0; }
6.分糖果
思路：
刚开始想到的是分为两个数组，一个数组里面放输入的数，另一个放应该输 出的。先让第二个数组里面全为1，即保证每个人分到一个糖果，然后在遍历，如 果前面的数大于后面的，则相应的数组里面加一，但是只能保证一轮里面只有1和 2，能过简单的样例，没有考虑到还有会三个糖的，所以遍历一遍远远不够，然后 开始跑偏，写不出来了...时间截止了... 将前面一个的糖果和后面一个的糖果联系起来。
#include <bits/stdc++.h> #pragma GCC optimize(3,"Ofast","inline") #define re register #define ll long long #define ull unsigned long long #define r read() using namespace std; //速读 inline int read() { int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } int s[10000]; int cnt[10000]; ll ans = 0; int main() { ios::sync_with_stdio(false); int n = r; for(int i = 1; i <= n;i++){ s[i] = r; //每个人的评分 cnt[i] = 1; //每个人至少一个糖果 } for(int i = 2; i <= n; i++){ if(s[i]-s[i-1]> 0){ //如果右边的比左边大，则右边的糖果比左边的糖果多一个 cnt[i] = cnt[i-1] + 1; } } for(int i = n; i >= 2; i--){ //从右往左循环一次，如果左边比右边大，则左边比右边要多一个糖果 if(s[i]-s[i-1] < 0){ if(cnt[i] >= cnt[i-1]){ cnt[i-1] = cnt[i] + 1; } } } for(int i = 1;i <= n; i++){ //把所有糖果加起来 ans += cnt[i]; } cout<<ans<<endl; for(int i = 1; i <= n; i++){ cout<<cnt[i]; if(i != n){ cout<<" "; } } return 0; }
关于第二个for循环： for example：输入5个人的评分为：1 4 7 2 1， 第一个for循环分到的结果为：1 2 3 1 1，但显然评分为2的那个boy原本要比 最后一个小伙子分到的多，但是由于他比左边的要小，所以并不能加糖果，于是 聪明的我，又从后面来了一次遍历，把boy的糖果给补上了，才能得到最终的结果。
