SRM401div2题解
DIV2：
250：水题，题意是给定两个点的坐标，问连接这俩个点坐标的线段经过了多少整点 解法：gcd(x2-x1, y2-y1)-1
500：dp，题意是给定一个值fieldOrder，求非增序列且第k个数小于fieldOrder-k+1的个数 ?解法：dp[i][j] 表示第i个数大小是j的时候序列的个数 dp[i+1][k] += dp[i][j](k<=j,j<=fieldOrder-i+1)结果就是dp[i][j](j<=i)所有的和
?
#include <iostream>#include <cstdio>#include <cstring>using namespace std;long long dp[40][40];class FIELDDiagrams { public: long long countDiagrams(int fieldOrder) { long long ans = 0; for (int i = 1; i <= fieldOrder; i++) dp[1][i] = 1; for (int i = 1; i <= fieldOrder; i++) for (int j = 1; j <= fieldOrder-i+1; j++) for (int k = 1; k <= j; k++) dp[i+1][k] += dp[i][j]; for (int i = 1; i <= fieldOrder; i++) for (int j = 1; j <= fieldOrder-i+1; j++) ans += dp[i][j]; return ans; }};1000：
?
?
?