This paper studies a class of linear regulator problem where the terminal payoff function is not necessarily quadratic. The value function for this problem is generally not quadratic and thus it can not be reduced to solving the corresponding matrix Riccati equation as for the standard linear quadratic regulator (LQR) problem. The computational method of direct iteration using the dynamic programming equations is computationally expensive. In this paper, a new computational method based on max-plus techniques is developed for this problem which is demonstrated to be more efficient and more accurate. In particular, three max-plus fundamental solutions are obtained which can be used as the kernel of max-plus integration with respect to the max-plus dual of the terminal payoff to generate the value function of the linear regulator problem.