BNU 51640 Training Plan【Dp】

Training Plan

Time Limit: 5000ms Memory Limit: 262144KB 64-bit integer IO format:  %lld      Java class name:  Main Prev  Submit  Status  Statistics  Discuss   Next

Type:  None   None Graph Theory      2-SAT     Articulation/Bridge/Biconnected Component      Cycles/Topological Sorting/Strongly Connected Component      Shortest Path          Bellman Ford         Dijkstra/Floyd Warshall      Euler Trail/Circuit      Heavy-Light Decomposition     Minimum Spanning Tree      Stable Marriage Problem      Trees     Directed Minimum Spanning Tree      Flow/Matching          Graph Matching             Bipartite Matching              Hopcroft–Karp Bipartite Matching              Weighted Bipartite Matching/Hungarian Algorithm          Flow              Max Flow/Min Cut             Min Cost Max Flow  DFS-like      Backtracking with Pruning/Branch and Bound      Basic Recursion     IDA* Search      Parsing/Grammar     Breadth First Search/Depth First Search      Advanced Search Techniques          Binary Search/Bisection         Ternary Search  Geometry      Basic Geometry     Computational Geometry      Convex Hull      Pick's Theorem Game Theory      Green Hackenbush/Colon Principle/Fusion Principle      Nim     Sprague-Grundy Number  Matrix     Gaussian Elimination      Matrix Exponentiation Data Structures      Basic Data Structures     Binary Indexed Tree      Binary Search Tree      Hashing     Orthogonal Range Search      Range Minimum Query/Lowest Common Ancestor      Segment Tree/Interval Tree     Trie Tree      Sorting      Disjoint Set String      Aho Corasick     Knuth-Morris-Pratt      Suffix Array/Suffix Tree Math      Basic Math     Big Integer Arithmetic      Number Theory         Chinese Remainder Theorem          Extended Euclid          Inclusion/Exclusion         Modular Arithmetic      Combinatorics          Group Theory/Burnside's lemma         Counting      Probability/Expected Value  Others     Tricky      Hardest     Unusual      Brute Force     Implementation      Constructive Algorithms     Two Pointer      Bitmask     Beginner      Discrete Logarithm/Shank's Baby-step Giant-step Algorithm      Greedy     Divide and Conquer  Dynamic Programming                   Tag it!

小Q同学为了准备今年的ICPC Regional，计划在天之内刷掉道题，每道题有一个难度值，其中第道题的难度值为。

然而处于半颓废状态中的小Q同学不希望在同一天中做难度差距悬殊的题目，定义第天中刷的题的难度的最大值减最小值为（如果第天没有刷题，则），那么整个计划的难度为。

小Q同学可以按照任意的顺序刷题，并且一天中可以刷任意多道题，但是每道题只需要做一次，现在小Q同学想知道完成这个计划的总难度的最小值是多少。

Input

第一行是一个正整数，表示测试数据的组数，

对于每组测试数据，

第一行是两个整数和，表示题数和天数，

第二行是个整数，表示每道题的难度值。

Output

对于每组测试数据，输出一个整数，表示整个计划的最小难度。

Sample Input

2 3 3 1 2 3 3 2 1 2 3

Sample Output

0 1

Hint

对于第一组样例，最优方案是一天刷一题。

对于第二组样例，一个最优方案是第一天刷难度值为1和2的题，第二天刷难度值为3的题。

Source

第十四届北京师范大学程序设计竞赛决赛

Author

hwq1352249 思路：

1、最优解问题，我们第一时间肯定要先想想贪心的。

那么贪心的去想的话，我们肯定要先将题目按照难度有序的排列一下。

接下来考虑最优解，那么我们哪个题作为一天的结尾对于之后的选择是有影响的，而不会对之前有影响，所以这里没有后效性。

而且考虑最优，我们考虑dp.

2、设定dp【i】【j】表示以第i道题作为第j天结尾的方案的最优解。

那么状态转移方程有：

dp【i】【j】=min（dp【i】【j】，dp【k】【j-1】+（a【i】-a【k+1】）^2）；

注意细节和初始化大小即可。

Ac代码：

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define INF 1000000000000000000 #define ll long long int ll a[515]; ll dp[515][515]; int main() { ll t; scanf("%lld",&t); while(t--) { ll n,m; scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++)scanf("%lld",&a[i]); sort(a+1,a+1+n); for(ll i=0;i<=513;i++) { for(ll j=0;j<=513;j++) { dp[i][j]=INF; } } dp[0][0]=0; for(ll i=1;i<=n;i++) { for(ll j=1;j<=m;j++) { for(ll k=0;k<i;k++) { dp[i][j]=min(dp[i][j],dp[k][j-1]+(a[i]-a[k+1])*((a[i]-a[k+1]))); } } } ll output=INF; for(ll i=1;i<=m;i++)output=min(dp[n][i],output); printf("%lld\n",output); } }