Sum
Consider the natural numbers from 1 to N. By associating to each number a sign (+ or -) and calculating the value of this expression we obtain a sum S. The problem is to determine for a given sum S the minimum number N for which we can obtain S by associating signs for all numbers between 1 to N.
For a given S, find out the minimum value N in order to obtain S according to the conditions of the problem.
Input
The only line contains in the first line a positive integer S (0< S <= 100000) which represents the sum to be obtained.
Output
The output will contain the minimum number N for which the sum S can be obtained.
Sample Input
12
Sample Output
7
Hint
The sum 12 can be obtained from at least 7 terms in the following way: 12 = -1+2+3+4+5+6-7.
Source
题目类型：线性DP
算法分析：dp[i][j]表示前1~i的数字通过加减运算是否能够表示成数字j，由于j可能会有负值，所以需要先加上一个偏移量，初始化dp[1][“0”+-1] = true，状态转移方程为dp[i][j] = dp[i-1][j-i] + dp[i-1][j+i]，可以使用奇偶滚动数组来优化空间，写成“我为人人型”会TLE
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
/************************************************** filename :h.cpp author :maksyuki created time :2017/2/12 12:30:31 last modified :2017/2/12 13:34:49 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CPPFF ifstream cin ("in") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 2e5; bool dp[2][maxn+1]; int main() { //CFF; //CPPFF; int S; while(scanf("%d", &S) != EOF) { memset(dp[1], false, sizeof(dp[1])); dp[1&1][maxn/2+1] = true; dp[1&1][maxn/2-1] = true; int res = -1; for(int i = 2; ; i++) { memset(dp[i&1], false, sizeof(dp[i&1])); for(int j = 0; j <= maxn; j++) { if(j - i >= 0) dp[i&1][j] |= dp[(i-1)&1][j-i]; if(j + i <= maxn) dp[i&1][j] |= dp[(i-1)&1][j+i]; } if(dp[i&1][S+maxn/2]) { res = i; break; } } printf("%d\n", res); } return 0; } |
题目类型：同余计算
算法分析：若所有的操作都是累加操作则最后的和是(1 + n) * n / 2，若还存在减法操作则记累减的和为s，则易知有(1 + n) * n / 2 - 2 * s = S，则可推得(1 + n) * n / 2和S关于2同余，则最后枚举n并判断即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
/************************************************** filename :i.cpp author :maksyuki created time :2017/2/12 13:46:56 last modified :2017/2/12 13:49:02 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CPPFF ifstream cin ("in") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; int main() { //CFF; //CPPFF; int n; while(scanf("%d", &n) != EOF) { int res = -1; for(int i = (int) sqrt((double)2 * n); ; i++) if(i * (i + 1) / 2 >= n && i * (i + 1) / 2 % 2 == n % 2) { res = i; break; } printf("%d\n", res); } return 0; } |
- « 上一篇：poj2392
- poj1745：下一篇 »